HDU 3988 Harry Potter and the Hide Story （数论）

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

该回到老本行，继续数学类学习，在这之前先做些题复习复习

这是一个多校题目。求最大的i使得n!%k^i为0。竟然能够整除，那说明k的质因子都会出现在n！中才行。

首先对k进行质因子分解，对于每一个质因子，k中出现的次数为c，而同样计算出n!中包括该质因子的个数s。那么i最大值就应该是s/c，s/c*c为k^i中包括该质因子个数，而s>=s/c*c，所以是一定能够整除的。

K的范围10^14，可以打10^7的素数表。也许出题人是想用随机算法的，不过素数表可以过。

还有种情况是inf,也就是i可以无穷大，很明显只有一种情况，那就是k为1

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100005
#define MOD 9973
#define LL unsigned long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
bool flag[10000005];
int cnt=0,prime[10000005];
void Init(){
	for(int i=2;i<=sqrt(10000000.0)+1;i++){
		if(flag[i])
			continue;
		for(int j=2;j*i<=10000000;j++)
			flag[i*j]=true;
	}
	for(int i=2;i<=10000000;i++)
		if(!flag[i])
			prime[cnt++]=i;
}
LL get_sum(LL n,LL p){
	LL ret=0;
	while(n){
		n/=p;
		ret+=n;
	}
	return ret;
}
int main(){
	int t,cas=0;
	scanf("%d",&t);
	Init();
	while(t--){
		LL n,k;
		scanf("%I64u%I64u",&n,&k);
		if(k==1){
			printf("Case %d: inf\n",++cas);
			continue;
		}
		LL mmax=-1;
		for(int i=0;i<cnt&&prime[i]<=k;i++){
			if(k%prime[i]==0){
				int c=0;
				while(k%prime[i]==0){
					c++;
					k/=prime[i];
				}
				LL tmp=get_sum(n,prime[i])/c;
				if(mmax==-1)
					mmax=tmp;
				else
					mmax=min(mmax,tmp);
			}
		}
		if(k>1){
			LL tmp=get_sum(n,k);
			if(mmax==-1)
				mmax=tmp;
			else
				mmax=min(mmax,tmp);
		}
		printf("Case %d: %I64u\n",++cas,mmax);
	}
	return 0;
}