题解 | #整除问题#

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int n,a;
    //n!=1*2*....*n
    //a=p1^k1*p2^k2*....*pn^kn
    
    //n!=p1^k1*p2^k2*....*pn^kn
    cin>>n>>a;
    unordered_map<int, int> n_primes;
    unordered_map<int, int> a_primes;
    for(int i=2;i<=n;i++){
        int j;
        int t=i;
        for(j=2;j<=t/j;j++){
            while(t%j==0){
                if(n_primes.count(j)){
                    n_primes[j]++;
                }else{
                    n_primes[j]=1;
                }
                t/=j;
            }
        }
        if(t>1){
            if(n_primes.count(t)){
                n_primes[t]++;
            }else{
                n_primes[t]=1;
            }
        }
    }
    for(int i=2;i<=a/i;i++){
        while(a%i==0){
            if(a_primes.count(i)){
                a_primes[i]++;
            }else{
                a_primes[i]=1;
            }
            a/=i;
        }
    }
    if(a>1){
        if(a_primes.count(a)){
            a_primes[a]++;
        }else{
            a_primes[a]=1;
        }
    }
    int k=0;
    bool flag = true;
    while(flag){
        for(auto a_p : a_primes){
            if(n_primes.count(a_p.first)&&n_primes[a_p.first]>=k*a_p.second){
                continue;
            }else{
                flag=false;
                break;;
            }
        }
        if(flag)k++;
    }
    cout<<k-1<<endl;
}
// 64 位输出请用 printf("%lld")