题目描述

SOL君很喜欢阶乘。而SOL菌很喜欢研究进制。

这一天，SOL君跟SOL菌炫技，随口算出了n的阶乘。

SOL菌表示不服，立刻就要算这个数在k进制表示下末尾0的个数。

但是SOL菌太菜了于是请你帮忙。

 

说明

对于20%的数据，n <= 1000000， k = 10

对于另外20%的数据，n <= 20， k <= 36

对于100%的数据，n <= 10^12，k <= 10^12

 

　　这道题的思路还是挺显然的，0的个数即n!和k共同质因数的数量之比最小的那个。K的质因数很容易在O(√k)的时间内统计出来，问题是N!中与K相同的质因子的个数怎么统计

　　我们令G(T,K)表示T中质因子K的个数，显然有：

　　　　G(N!,K)=G(1*2*....*N,K)=G(1*K*2*K*3*K*....*[N/K]*K,K)

　　我们对这个式子进一步变形：

　　　　G(1*K*2*K*3*K*....*[N/K]*K,K)=G(K^[N/K]*1*2*....*[N/K],K)=[N/K]+G([N/K],K)

　　接下来的问题接下来显然可以递归处理，易证G函数的复杂度是O(log N)

　　于是问题就那么1A了。（题目挺简单，但我特么调了半个钟精度。。。垃圾devc++(╯°Д°)╯︵ ┻━┻）

　　

#include
     
      using namespace std;#define MAXN 1000000+10typedef long long LL;const LL INF=1e13;LL n,k,ans=INF,cn[MAXN],ck[MAXN],prime[MAXN],fac[MAXN];bool isprime[MAXN];int cnt=0,tot=0,had[MAXN];void form(){    memset(isprime,true,sizeof(isprime));    isprime[1]=false;    for(int i=2;i<=MAXN-10;i++){        if(isprime[i])prime[++cnt]=i;        for(int j=1;j<=cnt&&i*prime[j]<=MAXN-10;j++){            isprime[i*prime[j]]=false;            if(i%prime[j]==0)break;        }    }    }void dealk(){    for(LL i=2;i*i<=k;i++)        if(isprime[i]&&k%i==0)fac[++tot]=i;    LL p=k;    for(int i=1;i<=tot;i++){        while(p%fac[i]==0){            had[i]++;            p/=fac[i];        }    }    if(p!=1)fac[++tot]=p,had[tot]++;}LL calc(LL p,LL t){    if(p==0)return 0;    LL f=(LL)p/t;    return f+calc(p/t,t);}int main(){    form();    scanf("%lld%lld",&n,&k);    dealk();    for(int i=1;i<=tot;i++){        LL p=calc(n,fac[i]);        p/=had[i];        ans=min(ans,p);    }    printf("%lld\n",ans);    return 0;}
     

 　　吐槽一波：洛谷的题目相比雅礼集训的简直小清新2333333