ABC280D - Factorial and Multiple 题解 二分 + 勒让德公式

题目链接：https://atcoder.jp/contests/abc280/tasks/abc280_d

解题思路：

首先对 \(K\) 进行质因数分解，然后二分 \(N\)，判断 \(K\) 的每个质因数的次数是否都 \(\le n！\) 中包含的这个质因子的次数即可。

示例程序：

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

ll s(ll n, ll p) {
    ll res = 0;
    for (; n; n /= p)
        res += n % p;
    return res;
}

ll legendre(ll n, ll p) {
    return (n - s(n, p)) / (p - 1);
}

ll p[100], k, n, l, r;
int c[100], m;

void init(ll k) {
    for (ll i = 2; i * i <= k; i++) {
        if (k % i == 0) {
            p[++m] = i;
            for (; k % i == 0; k /= i)
                c[m]++;
        }
    }
    if (k > 1) {
        p[++m] = k;
        c[m] = 1;
    }
}

bool check(ll n) {
    for (int i = 1; i <= m; i++)
        if (legendre(n, p[i]) < c[i])
            return false;
    return true;
}

int main() {
    cin >> k;
    init(k);
    l = 1, r = k;
    while (l <= r) {
        ll mid = l + r >> 1;
        if (check(mid))
            n = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    cout << n << endl;
    return 0;
}