数论题目。有关内容:整数质因数分解，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)//对m进行质因数分解
{
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;
}