Double Factorial [AtCoder Beginner Contest 148 E]

https://atcoder.jp/contests/abc148/tasks/abc148_e

解説

https://atcoder.jp/contests/abc148/submissions/9103493

大学受験を済ませている人は、この問題を見たらピンと来るかもしれない。
ある数の末尾に続く0の個数はある数を素因数分解したときのmin(2の個数, 5の個数)となる。
これをベースとして考えていく。

するとNが奇数の場合は、かける全ての数に2を約数として含まないので、答えは0になる。
Nが偶数の場合は、
246810121416...
となっていく。
2はむちゃくちゃあるので、実質5の個数が答えの個数である。
15のように下1桁が5になることは無いので、10の倍数に5が含まれる可能性がある。
よって、いっぱいあるが、実際は10の倍数だけ考えれば良いことが分かる。
1020304050...
これは元々10の倍数なので、この個数分とりあえず10はある。
その個数を数えて、全部10で割ってやると、
12345...
となる。
ここまでくれば、センター試験で見たような問題と同じ問題になる。
5の倍数の個数+5²の倍数の個数+5³の倍数の個数+...を数えていけばいい。
あとは、それと元々10の倍数が何個あったかの和が答え。
オーバーフローするかもと思うが、あまりよく考えずに出すと通る。

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

    if (N % 2 == 1) {
        cout << 0 << endl;
        return;
    }
    
    ll ans = N / 10;
    N /= 10;

    ll p5 = 5;
    while (p5 <= N) {
        ans += N / p5;
        p5 = p5 * 5;
    }
    cout << ans << endl;
}