[AtCoder] ABC 148 E – Double Factorial

問題

方針

\( 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\]

となります。

コード