ABC057 C - Digits in Multiplication

備忘録

問題

atcoder.jp

回答

"use strict"
 
const f = (A, B) => {
  return Math.max(String(A).length, String(B).length);
}
 
function Main(input) {
  input = parseInt(input.trim(), 10);
  const max = Math.floor(Math.sqrt(input));
 
  let ret = 1e10;
  for(let i=1; i<=max; i++){
    if(input%i === 0){
      let A = input / i;
      let k = f(A, i);
      if(k < ret) ret = k;
    }
  }
 
  console.log(ret);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

考え方

1から√Nまでの数字でNの公約数をF(A, B)で試行し、最小値を取るだけ。
1からNまでの数字でNの公約数を求めた場合、たぶん時間超過になる。