Codeforces - 1114C - Trailing Loves (or L'oeufs?) - 简单数论

àì夳堔傛蜴生んèń 2021-09-30 11:06 101阅读 0赞

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

很有趣的一道数论，很明显是要求能组成多少个基数。

可以分解质因数，然后统计各个质因数的个数。

比如8以内，有8/2=4个2+8/4=2个2+8/8=1个2，这样统计是log复杂的。

需要小心的是乘法爆ll的情况，实际上改成**从最高的开始往下除**可以避免。

然后求这些质因数分解是b的质因数分解的几倍。

然后还有一个bug就是，当n!中缺少b的某个或全部因子时，问题很大。

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    
    ll n,b,cb;
    
    map<ll,ll> m;
    map<ll,ll> m2;
    
    void fenjieb(){
        m.clear();
        cb=b;
        ll ceil=sqrt(b+0.001);
        for(ll i=2;i<=ceil;i++){
            while(b%i==0){
                b/=i;
                m[i]++;
            }
        }
        if(b!=1)
            m[b]++;
        b=cb;
    }
    
    ll countd(){
        m2.clear();
        for(auto i:m){
            ll ii=i.first;
            ll cn=n;
            int cnt=0;
    
            //bug1
            while(cn>=i.first){
                cn/=i.first,cnt++;
            }
    
            for(int p=0;p<cnt;p++){
                m2[i.first]+=n/ii;
                //cout<<"+"<<ii<<": "<<n/ii<<endl;
                ii*=i.first;
            }
        }
    
        /*for(auto i:m){
            cout<<i.first<<": "<<i.second<<endl;
        }
    
        for(auto i:m2){
            cout<<i.first<<": "<<i.second<<endl;
        }*/
    
        ll minnum=0;
        if(!m2.empty()) //bug2
            minnum=(*m2.begin()).second;
        for(auto i:m){
            if(m2.count(i.first))    //bug3
                minnum=min(m2[i.first]/i.second,minnum);
            else
                return 0;
        }
    
        return minnum;
    }
    
    ll solve(){
        fenjieb();
        return countd();
    }
    
    int main(){
        while(cin>>n>>b){
            cout<<solve()<<endl;
        }
    }

转载于:https://www.cnblogs.com/Yinku/p/10416159.html