题解 | #整除问题#

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN = 1000;
vector<int> Prime;
bool IsPrime[MAXN];
void Select() {   //筛法求质数
    for (int i = 0; i < MAXN; ++i) {
        IsPrime[i] = true;
    }
    IsPrime[0] = IsPrime[1] = false;
    for (int i = 2; i < MAXN; ++i) {
        if (IsPrime[i]) {
            Prime.push_back(i);
            for (int j = i * i; j < MAXN; j += i) {
                IsPrime[j] = false;
            }
        }
    }
}
int main() {
    int n, a;
    Select();
    while (scanf("%d%d", &n, &a) != EOF) {
        vector<int> prime;
        for (int i = 0; Prime[i] <= n; ++i) {    //记录小于等于n的质数
            prime.push_back(Prime[i]);
        }
        int number[MAXN];   //记录n!各个质因数的个数
        memset(number, 0, sizeof(number));
        for (int i = 2; i <= n; ++i) {     //对2到n分别进行分解质因数，统计n!质因数个数
            int temp = i;
            for (int j = 0; j < Prime.size() && Prime[j] <= temp; ++j) {
                while (temp % Prime[j] == 0) {
                    ++number[j];
                    temp /= Prime[j];
                }
            }
        }
        int number_a[MAXN];    //记录a的各个质因数个数
        memset(number_a, 0, sizeof(number_a));
        bool flag = false;    //记录a包含的质因数是否已超过n包含的质因数
        for (int i = 0; i < Prime.size() && Prime[i] <= a; ++i) {   //对a分解质因数
            while (a % Prime[i] == 0) {
                if (i > prime.size() - 1)flag = true;
                a /= Prime[i];
                ++number_a[i];
            }
        }
        int k = 1000;
        if (!flag) {    //未超过
            for (int i = 0; i < prime.size(); ++i) {
                if (number_a[i] && k > number[i] / number_a[i])k = number[i] / number_a[i];
            }
        }
        else {
            k = 0;
        }
        printf("%d\n", k);
    }
    return 0;
}