(\)
(Description)
求 (N!) 在 (K) 进制表示下末尾 (0) 的个数。
- (N,Kin [1,10^{12}])
(\)
(Solution)
我又NC了
考虑何种情况(K)进制下会产生(0)，可以类比十进制下的情况，发现(2)和(5)的因数各一个就会产生一个(0)，这是因为(10=2^1 imes 5^1)。类比的，我们将(K)分解质因数：
[K=prod_{i=1}^M p_i^{t_i}
]
那么构成一个(0)的代价就是对于分解得到的每一个(p_i)，消耗(t_i)个(p_i)。
然后对分解得到的每一个质因数求一下(N!)里含有多少个即可，这个套路很常见，每次加上(N/p_i)，同时让(N=N/p_i)至(N=0)即可，加入统计出的(N!)里含有(g_i)个(p_i)。
[ans=min_{i=1}^M {lfloorfrac{g_i}{t_i}
floor}
]
(\)
(Code)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000010
#define R register
#define inf 9000000000000000ll
using namespace std;
typedef long long ll;
ll n,k,tmp,res,ans=inf,fac[N],cnt[N];
int main(){
scanf("%lld%lld",&n,&k);
tmp=sqrt(k);
for(R ll i=2;i<=tmp;++i)
if(k%i==0){
fac[++fac[0]]=i;
while(k%i==0) ++cnt[fac[0]],k/=i;
}
if(k!=1) fac[++fac[0]]=k,cnt[fac[0]]=1;
for(R int i=1;i<=fac[0];++i){
tmp=n; res=0;
while(tmp) res+=tmp/fac[i],tmp/=fac[i];
ans=min(ans,res/cnt[i]);
}
printf("%lld
",ans);
return 0;
}