因为阶乘不容易存储,所以要分块进行相除。
比如: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; }