Div Game [AtCoder Beginner Contest 169 D]

https://atcoder.jp/contests/abc169/tasks/abc169_d

前提知識

• 素因数分解(O(sqrt(N)))

解説

https://atcoder.jp/contests/abc169/submissions/13920513

今回の操作では以下のことが言える。

• 各素数pについて、割れる回数は独立に計算できる
• ある素数pについて、最適な割る操作は、p, p², p³, ...のようにすること

これが思いつけば、まず第一段階はクリア。
独立性については、色々な問題で出てくる考え方なので、頑張って思いついてもらうとして、
2つ目だが、操作を行う問題の取り組み方として、「最適な方針があるかも」として考えるのはテクである。
選択肢の1つとして覚えておこう。

この最適操作をやるというのが次のステップになるが、操作を考えると、Nの素因数分解が必要そうな感じに見える。
実は素因数分解はO(sqrt(N))で行うことができる。
ググろう。
N=10¹²というのから計算量O(sqrt(N))をメタ読みして、素因数分解にたどり着いてもいい。
自分はメタ読みが先だった。

あとは、各素数についてp, p², p³を割れなくなるまでシミュレートして、全体でやった回数をこたえると答え。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    auto ep = enumpr(N);

    int ans = 0;
    fore(p, ep) {
        int cnt = p.second;
        rep(i, 1, 1010) {
            if (i <= cnt) {
                ans++;
                cnt -= i;
            }
            else break;
        }
    }
    cout << ans << endl;
}