题解 P3927 【SAC E#1 - 一道中档题 Factorial】

· · 题解

一个数在十进制转k进制时，我们用短除法来做。容易发现，如果连续整除p个k，则末尾有p个0。

于是问题转化为n!能连续整除几个k。

我们先给k分解质因数，然后对于每个质因数，求出n!里有多少个质因数，然后如果k里有x个这个质因数，则求出的结果除以x。最后的答案为这些结果的最小值。

如何求n!里包含质因数的个数？由于n!是1乘到n，所以每p(p是质数)个数里一定有一个p，然后这些数中每p个里一定还有个p，以此类推即可算出。

时间复杂度约是θ(sqrt(k)log⁡n)。

#include<cstdio>
using namespace std;
long long n,k,p[200002],c[200002],ans;
int cnt;
int main(){
    scanf("%lld%lld",&n,&k);
    cnt=0;
    for(long long i=2;i*i<=k;++i)
    if(k%i==0){
        p[++cnt]=i;
        c[cnt]=0;
        while(k%i==0){
            ++c[cnt];
            k/=i;
        }
    }
    if(k>1){
        p[++cnt]=k;
        c[cnt]=1;
    }
    ans=20000000000000;
    for(int i=1;i<=cnt;++i){
        long long t=0,now=n;
        while(now)t+=now/=p[i];
        t/=c[i];
        if(t<ans)ans=t;
    }
    printf("%lld\n",ans);
    return 0;
}