本题求m的最大多少次幂是 n！的因子；
也就是质因子分解 n！中某一质因子个数与m中质因子个数比的最小值。
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 int sign[10010]; 6 int pri[10010]; 7 int tot; 8 int e2[10010][1500],e1[10010][1500]; 9 10 void getpri (){ 11 memset (sign,0,sizeof sign); 12 sign[0]=sign[1]=1; 13 for (int i=2;i*i<10000;i++){ 14 if (!sign[i]){ 15 for (int j=i*i;j<10000;j+=i){//cout<<"error"; 16 sign[j]=1; 17 } 18 } 19 } 20 tot=0; 21 for (int i=2;i<10000;i++) 22 if (!sign[i]) 23 pri[tot++]=i;//cout<<i<<" "; 24 } 25 26 int main (){ 27 int t; 28 int n,m,temp,ans; 29 getpri ();//cout<<tot; 30 memset (e2,0,sizeof e2); 31 memset (e1,0,sizeof e1); 32 for (int i=2;i<=10000;i++){ 33 temp=i; 34 for (int j=0;j<tot;j++){ 35 while (temp%pri[j]==0){ 36 e2[i][j]++; 37 temp/=pri[j]; 38 } 39 e1[i][j]=e1[i-1][j]+e2[i][j]; 40 } 41 } 42 cin>>t; 43 for (int casenum=1;casenum<=t;casenum++){ 44 cin>>m>>n; 45 ans=1000000; 46 for (int j=0;j<tot;j++){ 47 if (e2[m][j]) 48 ans=min (ans,e1[n][j]/e2[m][j]); 49 }//cout<<e1[0]<<" "<<e2[0]<<" "<<n%pri[0]; 50 cout<<"Case "<<casenum<<":"<<endl; 51 if (ans==1000000||ans==0) 52 cout<<"Impossible to divide"<<endl; 53 else 54 cout<<ans<<endl; 55 } 56 return 0; 57 }