AtCoder ABC 057 C - Digits in Multiplication (緑色, 300 点)

整数に関する問題でまずは直面する典型的な事柄を学べる教育的問題！！

例えば整数 が素数かどうかを判定するのは、実は から まで順に試し割りすればよいという話など。

ただ、現代の ABC なら灰色 diff になりそうである。

問題へのリンク

問題概要

正の整数 が与えられる。 を満たす正の整数 の組をすべて考えたときの、「 の桁数と の桁数のうちの最大値」の最小値を求めよ。

制約

• 

考えたこと

を満たすような を全探索すれば OK！！！！！

そしてそれは、基本的には の約数をすべて求めてください、というのとほとんど同じ問題。実は

• まで考えて
• % == 0 であれば
• として、 が候補になる

という感じ。なぜ までで良いか？それは、 と との間に暗黙の大小関係として が成立していると考えても差し支えない。そうすると とすると となるので矛盾する。

#include <iostream>
using namespace std;
const long long INF = 1LL<<60;

int calc_digit(long long n) {
    int res = 0;
    while (n > 0) {
        ++res;
        n /= 10;
    }
    return res;
}

int main() {
    long long N; cin >> N;
    long long res = INF;
    for (long long a = 1; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long b = N/a;
        long long tmp = max(calc_digit(a), calc_digit(b));
        res = min(res, tmp);
    }
    cout << res << endl;
}