AtCoder Beginner Contest 148：E - Double Factorial

問題
解法
解答

問題

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

解法

N が奇数のとき，答えは 0．なぜならば，f(N) は素因数に 2 と 5 を持たないから．

N が偶数のとき，f(N) が 5 で割れる回数が答えとなる（正確には 2 で割れる回数との min になるが，5 で割れる回数の方が圧倒的に小さいため）．これは，N / (2 * (5^k)) (1 <= k) の和になる（イメージ的には 2 ~ N の偶数のうち 5 で割れるもの， 25 で割れるもの，... の個数を計算していく感じ）．O(log_5(N))．