求最大的k 使得 m^k 能被n!整除
m^k就是让m的每个质因子个数增加了k倍，只要求得n!的质因子能让m增加多少倍就够了。当然这里要取增加倍数最少的。
木桶装水的量取决于最短的木板。
预处理2-n每个数的质因子情况，由于n有10000，前10000个素数有1000+个，所以维护前缀和不划算。
case只有500 所以干脆每次都算一遍。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<time.h>
#include<vector>
#include<map>
using namespace std;
struct node
{
int x,t;
}t,tzf[100001];
vector<node> v[100001];
vector<int> pri;
int id[100011];
bool vis[100011];
void sieve()
{
int m= (int)sqrt(200001+0.5);
memset(vis,0,sizeof(vis));
for(int i=2;i<=m;i++)
{
if(!vis[i])
{
for(int j=i*i;j<=10000;j+=i)
vis[j]=1;
}
}
for(int i=2;i<=10000;i++)
{
if(!vis[i])
{
pri.push_back(i);
}
}
}
void init(int n)
{
int id=n;
for(int i=0;pri[i]*pri[i]<=n&&i<pri.size();i++)
{
if(n%pri[i]==0)
{
t.x=pri[i];
t.t=1;
n/=pri[i];
while(n%pri[i]==0)
{
n/=pri[i];
t.t++;
}
v[id].push_back(t);
}
}
if(n>1)
{
t.x=n;
t.t=1;
v[id].push_back(t);
}
}
int sum[100005];
int main()
{
sieve();
for(int i=2;i<=10000;i++)
init(i);
int cas;
scanf("%d",&cas);
int ca=1;
while(cas--)
{
int n,m;
memset(sum,0,sizeof(sum));
scanf("%d%d",&n,&m);
printf("Case %d:\n",ca++);
int top=0;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
n/=i;
tzf[top].x=i;
tzf[top].t=1;
while(n%i==0)
{
n/=i;
tzf[top].t++;
}
top++;
}
}
if(n>1)
{
tzf[top].x=n;
tzf[top].t=1;
top++;
}
for(int i=2;i<=m;i++)
{
for(int j=0;j<v[i].size();j++)
{
int tmp=v[i][j].x;
int ttmp=v[i][j].t;
sum[tmp]+=ttmp;
}
}
int ans=0x7fffffff;
for(int i=0;i<top;i++)
{
int tmp=tzf[i].x;
int ttmp=tzf[i].t;
ans=min(ans,sum[tmp]/ttmp);
}
if(ans==0||ans==0x7fffffff) puts("Impossible to divide");
else cout<<ans<<endl;
}
return 0;
}
/*
1234
2 10
2 100
97 12
*/
uva 10780 Again Prime? No Time. 质因子乱搞,布布扣,bubuko.com
uva 10780 Again Prime? No Time. 质因子乱搞
原文：http://blog.csdn.net/t1019256391/article/details/38538379