Codeforces Manthan, Codefest 16 B. A Trivial Problem

n! の末尾に 0 が m 個並ぶような n を全て列挙せよ。

n! の末尾に続く 0 の個数を求めるには、n! = X*10^e と分解したときの e の値を求めればいい。 e は n! を素因数分解したときの 2 の指数と 5 の指数のうち小さい方と一致する。

n! が持つ素因数 p の個数を求めるには、1,2,3,...,n が持つ素因数 p の個数を逐次計算して累積していけばよい。

今回は必要ないが、n! が持つ素因数 p の個数を O(log n) で求める方法がある。詳しくはルジャンドルの定理で調べるといい。

2 の個数より 5 の個数の方が少ないから 5 だけ数えてもいいみたい。