[AtCoder] ABC 169 D – Div Game

2020年6月1日2020年12月14日

問題

方針

任意の素数 \( p\) について \( N \bmod p^m = 0\) となるような最大の正の整数 \( m \) が求められたとします。この素数 \( p\) に関して、操作回数を最大化するには、\( c = 1, 2, 3, \cdots \) と選べば良いので、

\[ \dfrac{n(n+1)}{2} \leq m\]

と満たす最大の \( n \) が操作回数となります。このような \(n\) は二分探索によって求めることができます。\( m \) の求め方は、\( \sqrt{N} \) までの範囲で探索すれば十分です。

コード

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

int bs(int a) {
    int l = 0;
    int r = 3 * a;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (m * (m + 1) <= 2 * a) {
            l = m;
        } else {
            r = m;
        }
    }
    return l;
}

int main() {
    ll N;
    cin >> N;
    vector<ll> a;
    ll t = N;
    for (ll i = 2; i * i <= N; i++) {
        int k = 0;
        while (t % i == 0) {
            t /= i;
            k++;
        }
        if (k != 0) a.push_back(k);
    }
    int ans = 0;
    if (t != 1) ans = 1;
    for (int i : a) {
        ans += bs(i);
    }
    cout << ans << "\n";
    return 0;
}