题解 | #整除问题#

#include<iostream>
#include <strings.h>
#include<vector>
#include<map>
using namespace std;
const int MAX = 1001;
int main() {
    //筛选1000以内的全部素数
    vector<int> primes;
    bool isPrime[MAX] ;
    for (int i = 0; i < MAX; i++) isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;
    for (int i = 0; i < MAX; i++) {
        if (isPrime[i] == true) {
            primes.push_back(i);
            for (int j = i * i; j < MAX; j += i) isPrime[j] = false;
        }
    }
    int n, a;
    while (cin >> n >> a) {
        map<int, int> n_PrimeNumMap;
        map<int, int> a_PrimeNumMap;
        //记录n！各质因子的幂指数
        for (int i = 2; i <= n; i++) {
            int temp = i;
            int index_prime = 0;
            while (temp > 1) {
                int prime = primes[index_prime];
                if (temp % prime == 0) {
                    n_PrimeNumMap[prime]++;
                    temp /= prime;
                } else index_prime++;
            }
        }
        //记录a中各质因子的幂指数
        int index_prime = 0;
        while (a > 1) {
            int prime = primes[index_prime];
            if (a % prime == 0) {
                a_PrimeNumMap[prime]++;
                a /= prime;
            } else index_prime++;
        }
        int min = 2147483647;
        //遍历a的各质因子，求n！中对应质因子幂指数与a的质因子幂指数之比的最小值
        for (auto it = a_PrimeNumMap.begin(); it != a_PrimeNumMap.end(); it++) {
            if (n_PrimeNumMap.find(it->first) ==
                    n_PrimeNumMap.end()) {//a中存在n！中不存在的质因子，此时a只能是0次幂
                min = 0;
                break;
            }
            if (min > n_PrimeNumMap[it->first] / it->second) {
                min = n_PrimeNumMap[it->first] / it->second;
            }
        }
        cout << min << endl;
    }
    return 0;
}// 64 位输出请用 printf("%lld")