题目：Harry Potter and the Hide Story
题意：给两个数n和k，找一个最大的i使得k^i能整除n!。这里的n与k都很大，10^18
思路的确还算简单，直接对K素因子分解，然后对于每一个素因子，找出在n!中的个数，然后对应相除，找最小的即可。
只是这里注意一点，就是n！中素因子p的个数一定不会超过LL，这个可以由等比公式求和证明，然后直接素因子分解解决。
- #include?<stdio.h>??
- #include?<stdlib.h>??
- #include?<string.h>??
- #include?<algorithm>??
- #include?<iostream>??
- ??
- using?namespace?std;??
- typedef?unsigned?long?long?LL;??
- ??
- const?int?Times=10;??
- int?N=550;??
- const?LL?INF=9223372036854775807ULL;??
- LL?ct,cnt;??
- LL?fac[N],num[N];??
- LL?gcd(LL?a,LL?b)??
- {??
- ????return?b??gcd(b,a%b):a;??
- }??
- LL?multi(LL?a,LL?b,LL?m)??
- {??
- ????LL?ans=0;??
- while(b)??
- ????{??
- ????????if(b&1)??
- ????????{??
- ????????????ans=(ans+a)%m;??
- ????????????b--;??
- ????????}??
- ????????b>>=1;??
- ????????a=(a+a)%m;??
- ????}??
- return?ans;??
- LL?quick_mod(LL?a,248); line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> ????LL?ans=1;??
- ????a%=m;??
- ????while(b)??
- ????{??
- ????????if(b&1)??
- ????????{??
- ????????????ans=multi(ans,a,m);??
- ????????????b--;??
- ????????}??
- ????????b>>=1;??
- ????????a=multi(a,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> ????}??
- return?ans;??
- }??
- bool?Miller_Rabin(LL?n)??
- if(n==2)?return?true;??
- if(n<2||!(n&1))?false;??
- ????LL?a,m=n-1,x,y;??
- ????int?k=0;??
- while((m&1)==0)??
- ????????k++;??
- ????????m>>=1;??
- for(int?i=0;?i<Times;?i++)??
- ????????a=rand()%(n-1)+1;??
- ????????x=quick_mod(a,m,n);??
- int?j=0;?j<k;?j++)??
- ????????????y=multi(x,n);??
- ????????????if(y==1&&x!=1&&x!=n-1)?false;??
- ????????????x=y;??
- if(y!=1)?true;??
- LL?Pollard_rho(LL?n,LL?c)??
- ????LL?x,y,d,i=1,k=2;??
- ????y=x=rand()%(n-1)+1;??
- while(true)??
- ????????i++;??
- ????????x=(multi(x,n)+c)%n;??
- ????????d=gcd((y-x+n)%n,153); background-color:inherit; font-weight:bold">if(1<d&&d<n)?return?d;??
- if(y==x)?return?n;??
- if(i==k)??
- ????????????y=x;??
- ????????????k<<=1;??
- void?find(LL?n,int?c)??
- if(n==1)?return;??
- if(Miller_Rabin(n))??
- ????????fac[ct++]=n;??
- return?;??
- ????LL?p=n;??
- ????LL?k=c;??
- while(p>=n)?p=Pollard_rho(p,c--);??
- ????find(p,k);??
- ????find(n/p,k);??
- LL?getNum(LL?p,LL?n)??
- ????LL?ans=0;??
- while(n)??
- ????????ans+=n/p;??
- ????????n/=p;??
- int?main()??
- int?t,tt=1;??
- ????LL?n,kk,minx;??
- ????scanf("%d",&t);??
- while(t--)??
- ????????scanf("%I64u%I64u",&n,&kk);??
- ????????printf("Case?%d:?",tt++);??
- if(kk==1)??
- ????????????puts("inf");??
- ????????????continue;??
- ????????ct=0;??
- ????????find(kk,120);??
- ????????sort(fac,fac+ct);??
- ????????num[0]=1;??
- ????????int?k=1;??
- int?i=1;?i<ct;?i++)??
- if(fac[i]==fac[i-1])??
- ????????????????++num[k-1];??
- else??
- ????????????{??
- ????????????????num[k]=1;??
- ????????????????fac[k++]=fac[i];??
- ????????????}??
- ????????cnt=k;??
- ????????minx=INF;??
- int?i=0;?i<cnt;?i++)??
- ????????????LL?tmp=getNum(fac[i],n)/num[i];??
- if(minx>tmp)?minx=tmp;??
- if(minx==INF)??puts("inf");??
- else???????????cout<<minx<<endl;??
- return?0;??
- } ?
