数论题目。有关内容:整数质因数分解，N的阶乘质因数分解，整除的判断。

这道题的题意是给你两个数n、m，要求你求出n！所能整除的m^k的最大值的k是多少。

由于数据范围：1<m<5000,1<n<10000。通过分析我们可知，当n在100 以上后n！早已超出了int甚至__int64的范围了。即使在int范围内，要算出n！和m^k然后依次遍历，这样会超时。

所以我们可以考虑将如果m能整除n！，那么m^k才会有可能整除n!。如果n！可以整除m，那么将m进行质因数分解后，所得的所有质因子应该在n！中出现，而且同一质因子n！所包含的个数应该

大于等于m中所含的个数，那么推广到m^k能整除n!也是这个道理。这里的关键就是将m和n！进行质因数分解，然后先判断n！中是否含有m中的所有质因数，若不能全部包含就说明m不能整除n！，否则

m可以整除n！。接着进行的操作就是，将 n！中所有的m的质因子的个数与m中的对应的质因子的个数进行相处，所得的商取最小值就是m^k的最大值中k的值。

例如 3!=3*2*1,若用2去整除它，则最大只能去2^1,因为2只含有2这一个质因子，而且3！只含有2^1,所以k最大为1。

#include<stdio.h>#include<math.h>#include<string.h>int prime[10010];int vis[10010];void prepare(){	int i,j;	for(i=2;i<10010;i++)		if(!vis[i])			for(j=i*i;j<10010;j+=i)				vis[j]=1;}int sieve(int x){	int i,j=0;	for(i=2;i<=x;i++)	{		if(!vis[i])		{			prime[j]=i;			j++;		}	}	return j;}int solve(int y,int s){	int ans=0,i;	for(i=y;i<=s;i*=y)		ans+=s/i;	return ans;}int main(){	int t,No=0;	scanf("%d",&t);	while(t--)	{		No++;		memset(prime,0,sizeof(prime));		memset(vis,0,sizeof(vis));		int m,n,p,i,j;		int l,num1,num2,num3;		int ans=0xffffff;		scanf("%d%d",&m,&n);		prepare();		p=sieve(m);			l=m;		for(i=0;l>1;i++)		{			num1=0;			while(l%prime[i]==0)			{				num1++;				l/=prime[i];			}			if(num1)			{				num2=solve(prime[i],n);				num3=num2/num1;				ans=ans>num3?num3:ans;			}		}		if(ans)		{			printf("Case %d:\n",No);			printf("%d\n",ans);		}		else		{			printf("Case %d:\n",No);			printf("Impossible to divide\n");		}	}	return 0;}

数论 UVA 10780