[AtCoder] ABC 148 E – Double Factorial

2019年12月23日2020年12月18日

問題

方針

\( N \) が奇数の場合、\( f(N) \) は奇数となるので、答えは \( 0 \) となります。ここで、\( N ! \) の末尾に続く \( 0 \) の個数を考えます。

これは、\( N! \) の \( 5 \) の素因数の個数を求めれば解くことができます。これは、 \( 5^m \leq N \) を満たす最大の \( m \) を用いて、

\[ \sum_{k = 1}^{m} \left\lfloor \dfrac{N}{5^{k}} \right \rfloor\]

と計算できます。ここで、偶数の場合を考えます。

\[f(N) = 2 \times 4 \times \cdots (N – 2) \times N \]

上記の場合と比べて、\( 5^k \) の倍数の個数は半分になるので、

\[v_k = \left\lfloor \dfrac{N}{5^{k}} \right \rfloor\]

とすると、

\[ \sum_{k = 1}^{m} \left \lfloor \dfrac{v_k}{2} \right \rfloor\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll N;
    cin >> N;
    if (N <= 9 || N % 2 == 1) {
        cout << "0\n";
        return 0;
    }
    ll ans = 0;
    ll t = 5;
    while (t <= N) {
        ll v = N / t;
        ans += v / 2;
        t *= 5;
    }
    cout << ans << "\n";
    return 0;
}