ABC148 E - Double Factorial - あっとのTECH LOG

問題原文

E - Double Factorial

問題要旨

$f(N) = N * (N - 2) * (N - 4) * ... * 2$ の末尾に $0$ が何個続くか求めよ。

$1 \leq N \leq 10^{18}$

考えるべきこと

$N$ が奇数の時には答えは0

$f(N)$ はいくつかの奇数の積になるため、末尾が２で割り切れることはない。よって、末尾に０が続くことはない。
なので、 $N$ が偶数のパターンのみ考えれば良い。

$f(N)$ が計算できたとして、どうやって末尾の0を数えるか？

末尾の0が増えるのは、「10」が作れた時。
よって、 $f(N)$ を素因数分解した時の、 2の個数と5の個数のうち、小さい方が答えになる。もっといえば、 $f(N)$ が5で割り切れる回数よりも、2で割り切れる回数の方が明らかに大きくなるので、「 $f(N)$ が5で何回割れるか」が答えになる。

どうやって5で割れる回数を数えるか？

当然 $f(N)$ を計算することはできない。
まずは簡単なバージョンとして、「 $N!$ が5で何回割れるか？」を考えてみる。
これは、 $1 ~ N$ のうち、(5で１回割れるものの個数) + (5で2回割れるものの個数) + (5で3回割れるものの個数)... となる。例えば [tex: 5³ = 125] なんかは、 5で1回割れるし、2回でも割れるし、3回でも割れるので、結果的に 5で３回割れる、と言うことができる。

奇数を数えないようにするには？

今回求めたいのは、 $N!$ の話ではなく、 $f(N)$ のようないわば一つ飛ばしの階乗」の場合を求める必要がある。
ここで、「奇数は $f(N)$ 」の中に出てこない」ので、 5や15などといった、「5で割れるけど奇数のもの」はカウントしてはいけないことがわかる。
これはいわば「カウントできるものが半分になる」のと同じなので、「(2 * 5¹で割れるものの個数) + (2 * 5² で割れるものの個数) + (3 * 5³ で割れるものの個数...)」が答えになる。

けんちょんさんの考え方

けんちょんさんがすごいわかりやすく書かれていた。 drken1215.hatenablog.com

$N$ が偶数の時、出てくる数字は全て偶数なので、当然全て２で割り切れる。
すると、 10 * 8 * 6 * 4 * 2 = 2⁵(5 * 4 * 3 * 2 * 1) = 2⁵(5!) みたいに階乗が出てくる。（すごい）

この考え方が先にできると、「2が一つも手に入らないから奇数の場合だとつくれない」と、スッと頭に入ってくる。こういう考え方ができるようになりたいですね。

実装

N = int(input())

if N % 2 == 1:
    print(0)
    exit()

ans = 0
d = 10
while d <= N:
    ans += N // d
    d *= 5

print(ans)

実装自体は非常に平易。

反省

ここからはコンテスト中の反省 - 初手実験コードを書いてしまった。
実験コードはぐっと睨むと規則性が見つかることも少なくない。けど、今回は「10だと1つ、100だと2つ数が増えるんだな」と安直な結論に達してしまった。
あくまでも先になんらかの思考ありき（例えば素因数分解）で実験をしていれば、迷走することはなかった。

簡単なパターンを考えなかった $f(N)$ から考えてしまった。よくみると明らかに階乗に似た形をしているのだから、先にそっちを考えるべきだった。下手な実験も相まって、結局規則性を見つけられなかった。問題を洗い出したものの、個別でなく、１つの大きな塊みたいな捉え方をしてしまった。はっきり言って問題の分解がまるでできてなかった。

『思考ベースで実験をする』
『簡単なパターンを使って、問題を分離することを考える』