GCPC2011 - A Faculty Dividing Powers - c++编程基础

题意是说给出n , k 求出最大的 i 使得 n! % k^i == 0 ...
假设最简单的情况...k是质数...要求 n! = 1*2*3...*n ...易看出在k的倍数里..有1个k..在k的平方的有2个k..在k的立方中有3个k... 那么 n! 中k的个数为 n/k+n/(k^2)+n/(n^3)....及为最大的 i ...
拓展一步..若k非质数..但只有一个质因子..如8，9，125 之类的...可以先求出在 n! 中有多少个其质因子,设为x...那么有多少个k..就是 i = x/p...p是指k为起质因数的多少次方..
最终拓展出题目所要求的任意数的情况..k=a1^k1 * a2^k2 * a3^k3...an^kn 其中a1,a2...an为质数..可以算出n!中有多少a1,a2,a3...an...而组成一个k需要k1个a1..k2个a2..kn个an..那么也就是说n(a1)/k1 , n(a2)/k2 .... n(an)/kn...中最小的就是答案...

Program:
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#define ll unsigned long long
#define oo 1000000000
#define pi acos(-1)
using namespace std;
ll t,n,i,k,temp,m,ans,p[80000],a[105],b[105],num,g;
bool f[1000005];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
memset(f,true,sizeof(f));
for (t=2;t<=1000000;t++)
if (f[t])
for (k=t*2;k<=1000000;k+=t) f[k]=false;
m=0;
for (t=2;t<=1000000;t++)
if (f[t]) p[++m]=t;
cin>>t;
while (t--)
{
cin>>n>>k;
ans=0;
num=0;

temp=k;
for (i=1;i<=m;i++)
if (temp%p[i]==0)
{
a[++num]=p[i];
b[num]=0;
while (temp%p[i]==0)
{
temp/=p[i];
b[num]++;
}
}
if (temp!=1)
{
a[++num]=temp;
b[num]=1;
}
ans=(ll)(1e+18);
for (i=1;i<=num;i++)
{
temp=0;
g=a[i];
while (1)
{
temp+=n/g;
if (n/a[i]>=g) g*=a[i];
else break;
}
temp/=b[i];
ans=min(temp,ans);
}
cout< }
return 0;
}