10 が m! を割り切る最小の m は m=5 である。
25 が m! を割り切る最小の m は m=10 である。
n が m! を割り切る最小の m を s(n) とする。s(10)=5, s(25)=10 である。
2 ≤ i ≤ n において Σs(i) を S(n) とする。S(100)=2012 である。
S(10^8) を求めよ。
まずは与えられた例の吟味から。
- 10=2*5 が m! を割り切る最小の m は m=5
- 25=5^2 が m! を割り切る最小の m は m=10
「100! の末尾に0が何個並ぶか？」みたいなもので，n を素因数分解して p^k（p は素数）ごとに s を求め，その最大値をとればよいことがわかります。この方針でやってみたら240秒。
高速化するため，いくつかの素数についてははじめから最小値を与えてみました。
たとえば 5 なら 5, 10, 15, 20 を境に s が１ずつ増え，25=5^2 で 2 増えます。これは一般化できて，素数 p に対しては p^p が境になります。 p^p が 10^8 を超えない p に対してあらかじめ値を与えてみたら，20秒速くなって220秒になりました。
1分の壁は厚いです。10^8-1 個もの数を素因数分解しているのが原因なんでしょうね……