マツシタのお勉強

AtCoder ABC057 C - Digits in Multiplication

問題

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

整数N(1 <= N <= 1010)が与えられ、A * B = Nを満たすA, BについてF(A, B)の値が最小となるものを出力する問題。ここで、F(A, B)とはAとBの桁数を比べ小さい方の桁数を返り値する関数と定義されている。

解法

約数を全列挙する方法を考えてみる。整数iを1 ~ Nの範囲でforループさせ、Nがiで割り切れる時、A = i, B = N / iとなりA, Bを求める事ができる。F(A, B)は計算量1で求める事ができるので、全列挙した場合の計算量はO(N)となる。今回の問題ではNは最大で1010なので間に合わない。そこで計算量を減らす工夫を考える。

N = A * B = B * A という性質に注目する

N = A * B = B * Aという性質に着目することで計算量を大幅に減らす事ができる。N = 20の時を考えてみると、A = 4, B = 5の時とA = 5, B = 4の時のF(A, B)は同じ値を返す。つまり、Nの約数A, Bに関してA > Bとなる範囲は計算しなくて良いことが分る。

この条件でiの範囲を再定義すると、1 <= i <= sqrt(N) となる。(sqrt(N)はNの平方根)

これによって計算量はO(sqrt(N))となり、この問題を解くことができる。

ソースコード