ABC148 E - Double Factorial

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

初めてコンテスト本番で解けたE問題。

• 積の数字の個数→素因数分解の考え方は大事（今回は素因数分解しない）
• 2の因数は大量にあるので、5の因数の個数だけ調べれば良い

数弱だと数式の意味は分かりづらいが、サンプルを見ると分かる。要するに「偶数か奇数の積について0の個数がいくつ末尾に続くか」という問題。これは高校数学では有名な問題らしくググると解法が出てくるが、素因数分解して5の因数が何個あるか調べると答えが分かる。

0を作るには10を掛けるしかなく、要するに2×5が何個あるか調べれば良い。2の因数は必ず5の因数より多く出てくるため、5の因数が何個あるかだけ調べれば良い。積の数字の個数は素因数分解する定跡があるが、今回は素因数分解する必要はない。因数5の個数は毎にn個あることに注意してカウントし、偶数の場合は[1, N]までのうち因数5の半分となり、奇数の場合は因数2がないので常に答えは0になる。計算量はになる。