Trailing Loves (or L'oeufs?) [Codeforces Round #538 (Div. 2) C]

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

N!をB進数で表記したときに、末尾に0が何個続くか。
1≦N≦10^18
2≦B≦10^12

解説

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

Bを素因数分解したときに、p1^e1*p2^e2*...となったとする。
この時、N!を素因数分解したときに、p1が何個あるか、p2が何個あるかによって、Bを何個分作れるかが分かる。
このBの作れる個数がちょうど、答えの末尾の0の個数と一致する。
なので、まずはBを素因数分解しよう。
これはO(sqrt(B))でできる。
　
次は、N!にp1が何個あるかを計算する作業。
これは（1～Nのp1の倍数の個数）+（1～Nのp1^2の倍数の個数）+（1～Nのp1^3の倍数の個数）+...になる。
（1～Nのp1の倍数の個数）=N/p1なので、それぞれO(1)で計算ができ、p1=2でもp1^60くらいが限界なので、
各々計算しても間に合う。
ちなみに、このp1の指数部をインクリメントする過程でオーバーフローが起きうるので、オーバーフローしたら指定の最大値に丸める掛け算を行う必要がある。
　
最後にp1がn1個あった場合は、Bをn1/e1の切り捨て分作ることができるので、全ての素数について、これの最小値を取ると答えになる。

ll N, B;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> B;

    auto mp = enumpr(B);
    
    ll ans = infl;
    fore(p, mp) {
        ll pr = p.first;
        ll cn = p.second;

        ll x = pr;
        ll sm = 0;
        while (x <= N) {
            sm += N / x;
            x = mul(x, pr);
        }
        chmin(ans, sm / cn);
    }
    cout << ans << endl;

}