Codeforces 1114C(数论)

题面

传送门

分析

我们先考虑n!在10进制下有多少个0

由于10=2*5,

我们考虑n!的分解式中5的指数，答案显然等于(frac{n}{5}+frac{n}{5^2}+frac{n}{5^3}+dotsfrac{n}{5^k}(frac{n}{5^k}geq 1,frac{n}{5^{k+1}}<1))

可以用一个递归函数来计算：

ll f(ll x,ll y){
	if(x<y) return 0;
	else return x/y+f(x/y,y);
}

由于5的个数显然比2少，0的个数取决于5的个数

对于b进制下的0的个数

我们先把b质因数分解(b=prod p^{k_{i}}_{i})

对于每个质因数(p_i),我们按照递归函数求出n!中(p_i)的指数，然后再除以(k_i)

由于有指数影响，最大的质因数不一定出现的个数最小，不能像10进制那样直接计算

所以我们把每个质因数的结果取min即可

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#define maxn 1000005
using namespace std;
typedef long long ll;
ll n,base;
ll p[maxn],k[maxn]; 
int cnt=0;
void divide(ll x){
	ll sq=sqrt(x);
	ll ans=0;
	for(ll i=2;i*i<=x;i++){
		if(x%i==0){
			p[++cnt]=i;
			while(x%i==0){
				x/=i;
				k[cnt]++;
			}
		}
	}
	if(x>1){
		p[++cnt]=x;
		k[cnt]=1;
	}
} 
ll f(ll x,ll y){
	if(x<y) return 0;
	else return x/y+f(x/y,y);
}
ll count(ll n,ll x){
	divide(x);
	ll ans=0x7fffffffffffffff;
	for(int i=1;i<=cnt;i++){
		ans=min(ans,f(n,p[i])/k[i]);
	}
	return ans;
}
int main(){
	cin>>n>>base;
	cout<<count(n,base);
}