ABC057: C - Digits in Multiplication

問題

C: Digits in Multiplication - AtCoder Beginner Contest 057 | AtCoder

解答

N=A\times Bより、B=N\div Aとかける。ここで、対称性からA\le Bとして良い。 また、値を最小化したとき、桁数も最小化できる。 Bを最小化するためには、\sqrt NまでNを割り切る最大値Aを全探索すればよい。

int main() {
  ll N; cin >> N;
  ll a = 1;
  for (ll i = 1; i * i <= N; i++) {
    if (N % i == 0) {
      a = std::max(a, i);
    }
  }

  auto b = N / a;
  std::stringstream ss; ss << b;
  std::cout << ss.str().size() << "\n";
  
  return 0;
}