ABC 280

Table of Contents

D - Factorial and Multiple

https://atcoder.jp/contests/abc280/tasks/abc280_d

解説 AC

ルジャンドルの定理と二分探索で解く

ref: 予備ノリ 一度聞いたら忘れない『ルジャンドルの定理』の授業

ll f(ll n, ll p) {
    ll ans = 0;
    ll b = p;
    while (n / b) {
        ans += n / b;
        b *= p;
    }

    return ans;
}

void solve() {
    ll K;
    cin >> K;

    vector<pair<ll, ll>> div;
    {
        ll x = K;
        for (ll i = 2; i * i <= x; i++) {
            if (x % i != 0)
                continue;

            ll cnt = 0;
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
            div.emplace_back(i, cnt);
        }
        if (x != 1)
            div.emplace_back(x, 1);
    }

    ll ac = K, wa = 1;
    while (abs(ac - wa) > 1) {
        ll wj = (ac + wa) / 2;
        ll ok = 1;
        for (auto [p, cnt] : div) {
            if (f(wj, p) < cnt)
                ok = 0;
        }
        if (ok)
            ac = wj;
        else
            wa = wj;
    }

    cout << ac << endl;
}