AT_abc169_d [ABC169D] Div Game

看到题解里面好像没有用二分写的，我这个蒟蒻就写一个了。

题意

题目翻译写得很清楚了，我就不多写了。

思路

先把给定的 $N$ 分解质因数，得出：

$$N = a_1^{p_1} \times a_2^{p_2} \times a_3^{p_3} \times \dots \times a_k^{p_k}$$

我们分开算每一个 $a_i$，每一个的答案就是把 $p_i$ 分解成多个不同的正整数的个数的最大值，我们可以预处理出一个数组 $p$，定义 $p_i = (i – 1) \times i \div 2$，也就是前 $i$ 个正整数之和。

我们可以二分求出每一个 $p_i$ 的答案，注意不能用 lower_bound​ 减去 $1$，要用 upper_bound​ 再减去 $1$，因为用 lower_bound​ 的时候遇到 $x$ 刚好是 $p$ 中的一个数的时候会出现问题。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
#define int long long
long long N, a[1000005];
vector <int> p, e;
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N;
        if (N == 1) {
        cout << 0;
        return 0;
    }
    for (int i = 1; i <= 64; i ++) a[i] = i * (i + 1) / 2;
    for (int i = 2; i * i <= N; i ++) {
        // if (N == 1) break;
        int cnt = 0;
        while (N % i == 0) {
            cnt ++;
            N /= i;
            // cout << cnt << " " << i << " " << N << "\n";
        }
        if (cnt != 0) p.push_back(i), e.push_back(cnt);
    }
    int ans = 0;
    if (N != 1) p.push_back(N), e.push_back(1);
    for (int i = 0; i < e.size(); i ++) {
        ans += upper_bound(a + 1, a + 64 + 1, e[i]) - a - 1;
    }
    cout << ans;
    return 0;
}