1114C - Trailing Loves (or L'oeufs?) 〜階乗に含まれる素因数の数〜

Quiz

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

AC Code

https://codeforces.com/contest/1114/submission/56636163

map<ll, ll> factorize(ll n){
    map<ll, ll> mp;
    ll sq = sqrt(n);
    FOR(i, 2, sq+1){
        while(n%i==0){
            mp[i]++;
            n/=i;
        }
    }
    // 残り
    if(n!=1){
        mp[n]++;
    }
    return mp;
}

観察

• n!内にbがいくつ含まれるかが答え
• n, b共に値域が広く、O(N)では間に合わない

ルジャンドルの定理

• n! に含まれる素因数 p の数
• O(log n)で求まる
• https://mathtrain.jp/legendretheorem

素因数分解

• O(sqrt(b))で求まる

解法

• bを素因数分解
• 素因数ごとに、n!にいくつ含まれるかを数える
• n!からbをいくつ作れるかが求まるので、求めることができました