Digits in Multiplication [AtCoder Beginner Contest 057 C]

atcoder.jp

整数Nが与えられる。N=A*B と表せるような A,B のうち、桁数の大きいほうを F とする。Fのうち最小のものを出力せよ。という問題です。

Nが小さければ、1からNまで順番に調べていって、ある数 X が N の約数になっていれば、X と N/X を比較して桁数の大きいほうを minF に格納する……という手順で解くことができます。しかし今回の問題ではN は10^10なので、1からNまでを全て調べることはできません。

N=12 の場合を考えてみます。上記の方法で約数を全探索すると、

・1,12
・2,6
・3,4
・4,3
・6,2
・12,1

となります。前半と後半では並び順が違うだけで、数字は同じになってますね。今回の問題では A と B を区別する必要はないので、調べるのは前半部分だけでよく、後半部分を調べる必要はありません。ではどこまでがその前半部分なのかというと、sqrt(N) の小数部分を切り捨てたところまでです。12だと3まで。100だと10まで。入力例2にある1000003では1000まで調べればよいことになります。肝心のNの最大値である10^10では、100000まで。Javaであれば余裕で間に合いますね。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		long a = sc.nextLong();
		int n = (int)Math.sqrt(a);
		
		int min = Integer.MAX_VALUE;
		for (int i=1; i<=n; i++) {
			if (a%i==0) min = Math.max(String.valueOf(i).length(), String.valueOf(a/i).length());
		}
		
		System.out.println(min);
		
	}
}