けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 169 D - Div Game (400 点)

久しぶりに素因数分解する問題が来た!!!!!!!!!!!

問題へのリンク

問題概要

正の整数  N に対して、以下の操作を何回行うことができるか、その最大回数を求めよ。なお、素数  p と正の整数  e を用いて  p^{e} の形で表すことのできる整数を「素数べき」と呼ぶことにする。

  •  N の約数であるような素数べき  z を一つ選ぶ +ただし、過去の操作で選んだ整数は二度用いることはできない
  •  N \frac{N}{z} で置き換える

制約

  •  1 \le N \le 10^{12}

考えたこと

とても久しぶりに、素因数分解系の問題が来た!!!

qiita.com

まずこの手の問題でとても大切なことは

  •  N = p_{1}^{e_{1}} \times p_{2}^{e_{2}} \times \dots \times p_{K}^{e_{K}}

素因数分解したときに、 N の各素因数  p_{1}, p_{2}, \dots, p_{K} については完全に独立に考えて良いということがあると思う。今回でいえば単純に

  •  p_{1}^{e_{1}} についての最大操作回数
  •  p_{2}^{e_{2}} についての最大操作回数
  • ...
  •  p_{K}^{e_{K}} についての最大操作回数

をそれぞれ求めて、合計すれば OK!!!なお、素因数分解 O(\sqrt{N}) で実現できる。

N = pe の場合

というわけで問題は、 N 自身が素数べきである場合、すなわち、

  •  N = p^{e}

の場合を考えることに帰着された!!!

  •  e = 1 のとき、 z = p の 1 回のみ
  •  e = 2 のとき、 z = p をやると、 N = p になってもうダメなので 1 回だけ
  •  e = 3 のとき、 z = p, p^{2} の 2 回ができる
  •  e = 4, 5 のとき、重複なしだと  z = p, p^{2} の 2 回しかできない
  •  e = 6 のとき、 z = p, p^{2}, p^{3} の 3 回ができる
  • ...

という風になる。よって、以下の Greedy で求めることができる。


  •  z = p, p^{2}, p^{3}, \dots を順に試して行って
  • やれるところまでやる

なお、 N \le 10^{12} という制約から、 10^{12} は大体  2^{40} くらいなので、 e はどんなに大きくても 40 くらい。よって、愚直にやっても間に合う。

#include <bits/stdc++.h>
using namespace std;

// 素因数分解
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

int main() {
    long long N;
    cin >> N;
    auto pf = prime_factorize(N);
    long long res = 0;
    for (auto p : pf) {
        long long e = p.second;
        long long tmp = 0, cur = 1;
        while (e >= cur) e -= cur++, ++tmp;
        res += tmp;
    }
    cout << res << endl;
}