読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Manthan, Codefest 16 B. A Trivial Problem

codeforces.com

問題概要

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

解法

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

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

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

Codeforces Manthan, Codefest 16 B. A Trivial Probl ...

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