分解,尾零)"/>
Trailing Loves (or L'oeufs?)(唯一分解,尾零)
题目链接:
#include<cstdio>
#include<map>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e6+5;
bool p[N];
int prime[N],cnt=0;
void isprime(){p[0]=p[1]=true;for(int i=2;i<N;i++){if(!p[i]) prime[cnt++]=i;for(int j=0;j<cnt&&(ll)i*prime[j]<N;j++){p[i*prime[j]]=true;if(i%prime[j]==0) break;}}
}
map<ll,int> mp;
vector<ll> v;
int main(){isprime();ll n,b;scanf("%I64d%I64d",&n,&b);for(int i=0;i<cnt&&b!=1;i++){ //将b唯一分解int res=0;while(b%prime[i]==0){res++;b/=prime[i];}if(res) {mp[prime[i]]=res;v.push_back(prime[i]);}}if(b!=1) {mp[b]=1;v.push_back(b);}ll ans=999999999999999999;for(int i=0;i<v.size();i++){ //n!里有多少组b的因子就有多少尾0ll a=n;ll t=0;while(a>=v[i]){t+=a/v[i];a/=v[i];} ans=min(ans,t/mp[v[i]]);}printf("%I64d\n",ans);return 0;
}
更多推荐
Trailing Loves (or L'oeufs?)(唯一分解,尾零)
发布评论