题解 | 整除问题

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

int n, a;
map<int, int> reca;
map<int, int> recn;

int main() {
    // 打印素数表 欧拉筛 打印到1000以内够用了
    bool flag[1001];
    for (int i = 2; i <= 1000; i++)
        flag[i] = true;
    for (int i = 2; i <= 1000; i++) {
        if (flag[i]) {
            // 按照步长为i筛选
            for (int j = i + 1; j <= 1000; j = j + i) {
                if (j % i == 0)
                    flag[j] = false;
            }
        }
    }
    cin >> n >> a;
    for (int i = 2; i <= (int)(sqrt(a)); i++) {
        if (flag[i] && (a % i == 0)) {
            reca[i] = 0;
            while (a % i == 0) {
                a /= i;
                reca[i]++;
            }
        }
    }
    if (a > 1) reca[a] = 1; // 剩下一个大于sqrt(n)的质因子
    for (int i = 2; i <= n; i++) {
        if (flag[i]) {
            recn[i] = 0;
            int t  = n;
            while (t) {
                recn[i] += t / i;
                t /= i;
            }
        }
    }
    int rec = INT_MAX, k;
    for (auto it = reca.begin(); it != reca.end(); it++) {
        k = recn[it->first] / it->second;
        rec = min(rec, k);
    }
    cout << rec << endl;
    return 0;
}

整体的思路是质因数分解，对于a可以使用常规分解，对于n！使用勒让德定理进行计算，最好先打印一个素数表（欧拉筛）