Faculty Dividing Powers

Time Limit: 4000ms, Special Time Limit:10000ms, Memory Limit:65536KB

Total submit users: 40, Accepted users: 22

Problem 12500 : No special judgement

Problem description

Fred Faculty and Paul Power love big numbers. Day after day Fred chooses a random integer n and he computes n!. His friend Paul amuses himself by computing several powers of his randomly chosen integer k like k², k³ and so on. On a hot summer day, Fred and Paul got really, really bored, so they decided to play a joke on their buddy Dave Divider. Fred chooses a random integer n while Paul chooses a random integer k. They want Dave to find the biggest integer i such that kⁱ divides n! without a remainder, otherwise they will throw a cake in Dave's face. Because Dave does not like cakes in his face, he wants you to help him finding that integer i.

Input

The first line contains the number of test cases t (1 ≤ t ≤ 100). Each of the following t lines contains the two numbers n,k (2 ≤ n ≤ 10¹⁸, 2 ≤ k ≤ 10¹²) separated by one space.

Output

For each test case, print the maximum integer i on a separate line.

Sample Input

25 210 10

Sample Output

32

Judge Tips

Be careful with overflows in this problem (use 64 bit integers, avoid multiplications which will lead to overflow).

Problem Source

GCPC 2011

 

 

 

 题意是说给出n , k 求出最大的 i 使得 n! % k^i == 0 …

     假设最简单的情况…k是质数…要求 n! = 1*2*3…*n …易看出在k的倍数里..有1个k..在k的平方的有2个k..在k的立方中有3个k… 那么 n!  中k的个数为  n/k+n/(k^2)+n/(n^3)….及为最大的 i …

     拓展一步..若k非质数..但只有一个质因子..如8，9，125 之类的…可以先求出在 n! 中有多少个其质因子,设为x…那么有多少个k..就是 i = x/p…p是指k为起质因数的多少次方..

     最终拓展出题目所要求的任意数的情况..k=a1^k1 * a2^k2 * a3^k3…an^kn  其中a1,a2…an为质数..可以算出n!中有多少a1,a2,a3…an…而组成一个k需要k1个a1..k2个a2..kn个an..那么也就是说n(a1)/k1 , n(a2)/k2 …. n(an)/kn…中最小的就是答案…

 

 转自：

 

1 #include
     
       2 #include
      
        3 using namespace std; 4  5 bool p[1000010]; 6 __int64 precord[1000010]; 7 __int64 pcnt=0; 8 void init() 9 {10     memset(p,false,sizeof(p));11     for(int i=2;i<=500004;i++)                      //素数为false12         if(p[i]==false)13             for(int j=i+i;j<=1000009;j+=i)14                 p[j]=true;15     for(int i=2;i<=1000008;i++)16         if(p[i]==false)17             precord[pcnt++]=i;18 }19 20 __int64 min(__int64 a,__int64 b)21 {22     if(a>b)23         return b;24     return a;25 }26 27 __int64 krecord[100000];28 __int64 krecordcnt[100000];29 30 int main()31 {32     init();33     int t;34     __int64 n,k;35     scanf("%d",&t);36     while(t--)37     {38         memset(krecord,0,sizeof(krecord));39         memset(krecordcnt,0,sizeof(krecordcnt));40         scanf("%I64d%I64d",&n,&k);41         42         __int64 cnt=0;43         __int64 temp=k;44         for(int i=0;i
       
        temp)47                 break;48             if(temp%precord[i]==0)49             {50                 krecord[++cnt]=precord[i];51                 while(temp%precord[i]==0)52                 {53                     krecordcnt[cnt]++;54                     temp/=precord[i];55                 }56             }57         }58         if(temp!=1)59         {60             krecord[++cnt]=temp;61             krecordcnt[cnt]=1;62         }63 64         __int64 ans=-1;65         __int64 pp;66         __int64 count;67         for(int i=1;i<=cnt;i++)68         {69             pp=krecord[i];70             count=0;71             while(1)72             {73                 count+=n/pp;74                 if (n/krecord[i]>=pp)75                     pp*=krecord[i];76                 else77                     break;78             }79             count/=krecordcnt[i];80             if(ans==-1)81                 ans=count;82             else83                 ans=min(ans,count);84         }85         printf("%I64d\n",ans);86     }87     return 0;88 }