题意：判断m能否整除n！
题解：0特判，其他情况对m分解质因数并统计个数，看n！是否含多余该个数的质因数，n！关于质因数p的个数=(n/p+n/p^2+n/p^3......)，即求出mod p=0，mod p^2=0等的个数。
View Code 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 const int mr=65536; 7 bool notp[mr]; 8 int pr[mr]; 9 int pn; 10 void getpri()//筛素数 11 { 12 pn=0; 13 memset(notp,0,sizeof(notp)); 14 for(int i=2; i<mr; i++) 15 { 16 if(!notp[i]) 17 { 18 pr[pn++]=i; 19 } 20 for(int j=0; j<pn && i*pr[j]<mr; j++) 21 { 22 int k=i*pr[j]; 23 notp[k]=1; 24 if(i%pr[j]==0) 25 break; 26 } 27 } 28 } 29 int fac[1000],num[1000],top; 30 void div(int n) 31 { 32 for(int i=0,tp;i<pn&&pr[i]*pr[i]<=n;i++) 33 { 34 if(n%pr[i]==0) 35 { 36 num[top]=0; 37 tp=fac[top]=pr[i]; 38 while(n%tp==0) 39 { 40 n/=tp; 41 num[top]++; 42 } 43 top++; 44 } 45 } 46 if(n>1) 47 num[top]=1,fac[top++]=n; 48 } 49 int main() 50 { 51 getpri(); 52 int n,m; 53 while(scanf("%d%d",&n,&m)!=EOF) 54 { 55 if(m==0) 56 { 57 printf("%d does not divide %d!\n",m,n); 58 continue; 59 } 60 else if(m<=n||m==1) 61 { 62 printf("%d divides %d!\n",m,n); 63 continue; 64 } 65 top=0; 66 div(m); 67 bool flag=true; 68 for(int i=0;i<top;i++) 69 { 70 int t=num[i],p=fac[i],po=p; 71 while(t>0&&po<=n&&po>0) 72 { 73 t-=n/po; 74 po*=p; 75 } 76 if(t>0) 77 { 78 flag=false; 79 break; 80 } 81 } 82 if(flag) 83 printf("%d divides %d!\n",m,n); 84 else 85 printf("%d does not divide %d!\n",m,n); 86 } 87 return 0; 88 }
