人権なし

競プロで解いた問題や開発の進捗などの記録です

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)).

解答

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

f:id:babcs2035:20191222223338p:plain