AOJ 0052 （Factorial II : 階乗 II）

【問題】

https://onlinejudge.u-aizu.ac.jp/problems/0052

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0052

【解説】

n!の末尾の0の数を求める問題。nが最大で20000となるため、実際に階乗した末尾をカウントしようとするとlong型でも収まらないため、別の方針を立てる必要がある。

そこで、求めようとする「末尾の0の数」を言い換えると、これは、n!の因数における10の数である。よって、nを素因数分解した場合の2の数と5の数のうち、少ない方の数が10の数であるが、明らかに5の倍数の方が少ないため、nまでの数を素因数分解した場合の5の数を数えていけばよい。

25,125等は、素因数に5をそれぞれ複数含むため、数え漏れないように注意。

【コード】