約数ゲーム / Divisor Game [Ritsumeikan University Competitive Programming Camp 2019 Day 3 C]

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day3/problems/C

前提知識

• 素因数分解

解説

https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day3/3419470

実験しながら考察すると

• 最小回数は、素因数を1つだけ削った数だけ指定することで達成できる
• 最大回数は、全てのN以外の約数を指定できる

ことが分かる。
なので、素因数分解をして、素因数の個数が最小回数で、
各素因数の個数+1の総積が約数の個数となるので、-1したものが最大回数。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    auto ep = enumpr(N);

    int ans1 = ep.size();
    int ans2 = 1;
    fore(p, ep) ans2 *= (p.second + 1);
    ans2--;

    printf("%d %d\n", ans1, ans2);
}