题解 | #整除问题#

#include <map>
#include <string>
#include <iostream>
#include <cctype>
#include <stack>
#include <vector>
using namespace std;
//判断x是不是质数
bool isprime(int x) {
    if (x == 2) return true;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
int main() {
    //注意：质因数我们不考虑1
    int n, a;
    while (cin >> n >> a) {
        vector<int>aa(1000, 0);//存储a的质因数 aa[i]代表质因数i有aa[i]个
        vector<int>nn(1000, 0);//存储n的阶乘的所有质因数
        //求解a的质因数
        int tt = a;
        for (int i = 2; i * i <= a; i++) {
            if (isprime(i))
                while (tt % i == 0) {
                    aa[i]++;
                    tt /= i;
                }
        }
        //注意要检查一下最后的t是不是1，如果不是1，一定是一个质数，后面判断其实可以省略
        //举个例子 将26分解 2*13，tt=13,13还没被检测出来就跳出循环了，所以循环出来要判断一下
        //相反，如果是12，分解为2*2*3，出来的时候tt是1，所以不必处理
        if (tt != 1 && isprime(tt)) aa[tt]++;
        //求解2~n的质因数 ---与求解a的质因数类似，只是需要求解2到n每一个数的质因数，进行叠加
        for (int j = 2; j <= n; j++) {

            int t = j;
            for (int i = 2; i * i <= j; i++) {

                if (isprime(i))

                    while (t % i == 0) {
                        nn[i]++;
                        t /= i;
                        if (t == i) break;//如果最后分解的结果是两个质数相乘，跳出即可
                    }
            }
            if (t != 1 && isprime(t)) nn[t]++;
        }
        int k = 0;
        //举个例子 a是2*5 n!=2*3*4**5*6=2*3*2*2*5*2*3
        //我们尝试去遍历a的每一个质因子，然后看看n!对应的质因子数目是a的多少倍，k就是其中的最小值,类似于短板效应
        //比如a有一个质因子2，一个质因子5，而n!虽然有4个质因子2，却只有一个质因子5，显然k应取决于质因子5的倍数关系，k至少也是0，所以初始化为0
        for (int i = 0; i < 1000; i++) {
            if (aa[i] > 0) {
                if (k == 0) k = nn[i] / aa[i];
                else k = min(nn[i] / aa[i], k);
            }
        }
        cout << k << endl;
    }
}
// 64 位输出请用 printf("%lld")