perogram

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)では間に合わない

ルジャンドルの定理

素因数分解

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

解法

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