题解 | #整除问题#

#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<int> getPrimes(int max) {
    vector<int> primes;
    bool num[max + 1];
    for (int i = 2; i <= max; i++) {
        num[i] = true;
    }
    num[0] = num[1] = false;
    for (int i = 2; i <= max; i++) {
        if (num[i] = true) {
            primes.push_back(i);
            for (int j = i * i; j <= max; j += i) {
                num[j] = false;
            }
        }
    }
    return primes;
}
int main() {
    int n, a;
    vector<int> primes = getPrimes(1000);
    while (cin >> n >> a) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        map<int, int> n_primeCount; //质因数，幂次数
        map<int, int> a_primeCount;
        for (int i = 2; i <= n; i++) {
            int temp = i;
            for (auto prime : primes) {
                if (prime > temp) break;
                while (temp % prime == 0) {
                    n_primeCount[prime]++;
                    temp /= prime;
                }
            }
        }
        for (auto prime : primes) {
            if (prime > a) break;
            while (a % prime == 0) {
                a_primeCount[prime]++;
                a /= prime;
            }
        }
        int min = 2147483647;//寻找幂次数之比最小值
        for (auto it = a_primeCount.begin(); it != a_primeCount.end(); it++) {
            if (n_primeCount.find(it->first) == n_primeCount.end()) {//N!的质因数中不存在a的质因数
                min = 0;
                break;
            }
            if (n_primeCount[it->first] % it->second != 0) {//n!的质因数的幂次数不能被a的质因数的幂次数整除
                min = 0;
                break;
            }
            int temp = n_primeCount[it->first] / it->second;
            if (temp < min) min = temp;
        }
        cout << min << endl;
    }
}
// 64 位输出请用 printf("%lld")