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

問題概要

正の整数 $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 = p^e の場合

というわけで問題は、 $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;
}

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

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

AtCoder ABC 169 D - Div Game (茶色, 400 点)

問題概要

制約

考えたこと

N = p^e の場合

問題概要

制約

考えたこと

N = pe の場合

N = p^e の場合