https://codeforces.com/contest/1114/problem/C

题意

给你一个数n(<=1e8),要你求出n!在b进制下的后缀零个数(b<=1e12)

题解

• a在b进制下的后缀零个数?

  \(a=p_1^{x_1}*p_2^{x_2}*p_3^{x_3}...*p_n^{x_n}\),
  
  \(b=q_1^{y_1}*q_2^{y_2}*q_3^{y_3}...*q_n^{y_n}\)
  
  p,q为素因子,后缀零个数为min(floor(\(x_i/y_i\)))

• 求p在n!中的个数?
  

  求1~n有多少个数有\(p\),\(p^2\),\(p^3\),...,\(p^k<n\)

    for(i=0;i<p.size();i++){

        x=p[i];

        tp=0;

        while(x<=n){

            tp+=n/x;

            if(n*1.0/x>=p[i])x*=p[i];

            else break;

        }

        ans=min(tp/X[i],ans);

    }

代码

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n,b,i,ans=0,tp,x;

vector<ll>a;

ll X[100],sz,pr[1000005],num,vi[1000005];

void init(){

    for(ll i=2;i<=1e6;i++){

        if(!vi[i]){

            pr[num++]=i;

            for(ll j=0;j<num&&i*pr[j]<=1e6;j++){

                vi[pr[j]*i]=1;

                if(i%pr[j]==0)break;

            }

        }

    }

}

int main(){

    init();

    cin>>n>>b;tp=b;

    for(i=0;i<num;i++){

        if(tp%pr[i]==0){

            while(tp%pr[i]==0){

                tp/=pr[i];X[sz]++;

            }

            a.push_back(pr[i]);

            sz++;

        }

        if(tp==1)break;

    }

    if(tp>1){

        a.push_back(tp);

        X[sz]++;

    }

    ans=1e18;

    for(i=0;i<a.size();i++){

        x=a[i];

        tp=0;

        while(x<=n){

            tp+=n/x;

            if(n*1.0/x>=a[i])x*=a[i];

            else break;

        }

        ans=min(tp/X[i],ans);

    }

    cout<<ans;

}