摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 模仿 d122. Oh! My Zero!!

當我們要知道N!裡有幾個A的幾次方時,(A是質數)

有一個算法是說 假使答案是A^t

那麼t=(int)N/A+(int)N/(A^2)+(int)N/(A^3)+... (N/A^?=0 停止)

所以我們必須先將M分解得到質因數...然後去看次方

/**********************************************************/

#include<stdio.h>  
#include<stdlib.h>  
#include<math.h>  
int Prime[5200]={0},p;  
int prime()  
{  
  char num[5001]={0};  
  int a,b,m=0;  
 for(a=2;a<5000;a++)     
      if(num[a]==0)     
        {     
           Prime[m]=a;     
           m++;     
           for(b=2;a*b<=5000;b++)     
             num[a*b]=1;     
        }  
   return m;  
}  
int value[50],T[50],top;
int Divisors (int num)
{
   int a,b,C=1;
   for(a=0;a<p&&Prime[a]*Prime[a]<=num&&num!=1;a++)
      {
        int time=0;
        if(num%Prime[a]==0)
          {
             while(num%Prime[a]==0)
                {
                   num/=Prime[a];
                   time++;
                }
             ++top;
             value[top]=Prime[a];
             T[top]=time;
          }
      }
    if(num!=1)
       {
             ++top;
             value[top]=num;
             T[top]=1;
       }
    return C;
}
main()  
{  
 p=prime(); 
 int t,n,m,a,time=0; 
  /*freopen("input.txt", "rt", stdin);
  freopen("output.txt", "w+t", stdout);*/
 scanf("%d",&t);
   while(t--)
    {
       scanf("%d %d",&n,&m);
       top=0;
       Divisors (n);
       int MIN=2147483647;
       for(a=1;a<=top;a++)
          {
            int sum=0,temp=value[a];
            while(temp<=m)
               {
                 sum+=m/temp;
                 temp*=value[a];
               }
            if(sum/T[a]<MIN) MIN=sum/T[a];
          }
       printf("Case %d:\n",++time);
       if(MIN==0) printf("Impossible to divide\n");
       else printf("%d\n",MIN);
    }
 return 0;     
}