题解 | #整除问题#

//利用质因数分解的方法
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
using namespace std;

const int maxn = sqrt(1000) + 1;

vector<bool> isPrime(maxn, true);

vector<int> prime;

map<int, int> factorial;

map<int, int> prime_factor_a;

void Initial(){
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i < maxn; i++){
        if(!isPrime[i]) continue;
        else {
            prime.push_back(i);
            for(int j = i * i; j < maxn; j += i){
                isPrime[j] = false;
            }
        }
    }
}

void find_prime_factor(map<int, int>& prime_map, int n){
    for(int i = 0; i < prime.size() && prime[i] <= n; i++){
        while(n % prime[i] == 0){
            n /= prime[i];
            prime_map[prime[i]]++;

        }
    }
    if(n > 1) prime_map[n]++;
}

int main() {
    Initial();
    int n, a;
    cin >> n >> a;
    for(int i = 2; i <= n; i++){
        find_prime_factor(factorial, i);
    }
    find_prime_factor(prime_factor_a, a);
    int ret = factorial[prime_factor_a.begin()->first] / prime_factor_a.begin()->second;
    for(auto it : prime_factor_a){
        ret = min(ret, factorial[it.first] / it.second);
    }
    cout << ret;
}
// 64 位输出请用 printf("%lld")