因为阶乘不容易存储,所以要分块进行相除。
比如:n=5:5!=5 * 4 * 3 * 2 * 1,a=2;
a里边只有一个质因数2,所以我们要看5!里有几个质因数2。
对5、4、3、2、1分别取质因数并相加,得到共有4/2/2和2/2三个质因数2,所以k=3.
如果含有多个质因数,那么找n!中除以a的质因数中除数最小的。

#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main(){
    vector<int> vec;//素数筛子,记录素数
    bool isprime[1001];
    for(int i=0;i<1001;i++)isprime[i]=true;
    isprime[0]=isprime[1]=false;
    for(int i=2;i<1001;i++){
        if(!isprime[i]){
            continue;
        }vec.push_back(i);
        for(int j=i*i;j<1001;j+=i){
            isprime[j]=false;
        }
    }
    int n,a;
    map<int,int> mp;//存n!里的质因数
    map<int,int> mpa;//存a里的质因数
    while(cin>>n>>a){
        mp.clear();mpa.clear();
        for(int i=2;i<=n;i++){ //统计n!里的质因数
            int temp=i,j=0;
            while(temp!=1){
                if(temp%vec[j]==0){
                    mp[vec[j]]++;
                    temp/=vec[j];
                }else j++;
            }
        }int j=0;
        while(a!=1){ //统计a里的质因数
            if(a%vec[j]==0){
                mpa[vec[j]]++;
                a/=vec[j];
            }else j++;
        }int min=100000;
        for(auto it=mpa.begin();it!=mpa.end();it++){ //统计质因数里最少的
            if(mp.find(it->first)==mp.end()){
                min=0;break;
            }
            if(min>mp[it->first]/it->second){
                min=mp[it->first]/it->second;
            }
        }
        cout<<min<<endl;
    }
    return 0;
}