【Codeforces Round #538 (Div. 2) C. Trailing Loves (or L'oeufs?)】 分解质因数

C. Trailing Loves (or L’oeufs?)

题意

求$n!$在b进制下末尾有多少个$0$
$1\le 10\le 10^{18},2\le b\le 10^{12}$

做法

这道题我们首先考虑$10$进制，那就是看$n!$能够整除$5$多少次和整除$2$多少次。取个$min$即是答案，这道题做法类似，我们只需要先对$b$进行分解质因数，对每个质因数统计在$b$中出现次数$cnt$和在$n！$中出现次数$m$，最后对所有的$m/cnt$取$min$即可

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
ll solve(ll a,ll b)
{
    if(a==0) return 0;return a/b+solve(a/b,b);
}
int main()
{
    ll a,b;scanf("%lld%lld",&a,&b);ll ans=LL_INF;for(ll i=2;i*i<=b;i++){
    if(b%i==0){
    int cnt=0;while(b%i==0){
    cnt++;b/=i;}ans=min(ans,solve(a,i)/cnt);}}if(b>1)  ans=min(ans,solve(a,b));printf("%lld\n",ans);return 0;
}