題意是說給出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<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stack>
#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<<ans<<endl;
}
return 0;
}
