1 //Accepted    420K    16MS 2 //考虑 0和n！    does not divide 3 //      1和0！  divides 4 #include <cstdio> 5 #include <cstring> 6 #include <iostream> 7 using namespace std; 8 const int imax_n = (1<<16)+5; 9 int pri[imax_n];10 int cnt;11 void prime()12 {13     for (int i=2;i<imax_n;i++)14     {15         if ((long long )i*i<(long long )imax_n)16         for (int j=i*i;j<imax_n;j+=i)17         {18             pri[j]=1;19         }20     }21     cnt=0;22     for (int i=2;i<imax_n;i++)23     if (pri[i]==0)24     pri[cnt++]=i;25 }26 int getNumber(int n,int k)27 {28     int ans=0;29     if (k==0) return -1;30     while (n>0)31     {32         ans+=n/k;33         n/=k;34     }35     return ans;36 }37 int split(int n,int m)38 {39     int t;40     //printf("n=%d\n",n);41     if (n==0) return 0;42     if (m==0)43     {44         if (n==1) return 1;45         return 0;46     }47     for (int i=0;i<cnt && (__int64 )pri[i]*pri[i]<=(__int64 )n;i++)48     {49         if (n%pri[i]==0)50         {51             //printf("pri=%d\n",pri[i]);52             t=0;53             while (n%pri[i]==0)54             {55                 t++;56                 n/=pri[i];57             }58             int temp=getNumber(m,pri[i]);59             //printf("temp=%d t=%d\n",temp,t);60             if (temp<t) return 0;61         }62     }63     if (n!=1)64     {65         int temp=getNumber(m,n);66         if (temp<1) return 0;67     }68     return 1;69 }70 int main()71 {72     prime();73     int n,m;74     while (scanf("%d%d",&n,&m)!=EOF)75     {76         int ans=split(m,n);77         if (ans==1)78         {79             printf("%d divides %d!\n",m,n);80         }81         else82         {83             printf("%d does not divide %d!\n",m,n);84         }85     }86     return 0;87 }