数学A / 整数の性質
100! の末尾に並ぶ0の個数(素因数の個数)
問題
()を計算すると、末尾に が連続して何個並ぶか求めよ。
ヒントを見る
末尾の の個数 因数 の個数 。 の方が多いので の個数を数える。 の倍数は を2個持つことに注意。
解答・解説
方針
末尾の は の因子の数、すなわち 。 は より多いので の個数を数える。 の倍数を段階的に数える。
解答
⓪ 発想 — どう考え始めるか。 末尾の の個数は、 が で何回割れるかで決まる。 だから、答えは「因数 の個数」と「因数 の個数」の小さい方だ。
には偶数がたくさんある。因数 は明らかに より多いので、少ない方= の個数を数えればよい。
数え方にもコツがある。 の倍数は を 個ずつ持つが、 の倍数はもう 個余分に持つ。段階的に数え足すのが正確だ。
① の個数 の個数。 末尾の の個数 。偶数は 個以上あり の個数は の個数より多いので、 の個数を数えればよい。
② の個数を段階的に。 で
- の倍数は 個(それぞれ を少なくとも 個持つ)、
- の倍数は 個(さらにもう 個ずつ持つ)、
- の倍数は 個。
③ 合計。 の因数は よって末尾に は 個並ぶ。
まとめ 末尾の は因数 の個数(少ない方)。 の倍数を段階的に数えて 。整数(素因数)と数え上げの融合。 の倍数を二重に数えるのが急所。
発展 — 一歩先へ。 因数 の個数は、 が の倍数をまたぐ瞬間に 以上ジャンプすることがある。実際 までは 個、 で一気に 個。だから「末尾にちょうど 個の が並ぶ 」は存在しない。届かない個数がある — 床関数の和ならではの現象だ。
末尾の の個数 に含まれる素因数 の個数 。
別解
別解 — 桁和の公式で一撃(得意な人向けの高い視点)。 階乗に含まれる素因数 の個数には、 進法を使った閉じた公式がある。
を 進法で書いたときの桁の和を とすると、 に含まれる因数 の個数は になる(床関数の和 を桁ごとに整理すると、各桁が等比数列の和を作ることから出る)。
は 進法で ()。桁和は だから
床関数を 段ずつ足す本解と同じ が、桁の情報だけから出る。 でも は 進法で 、桁和 で と即答できる。
ポイント
- 末尾の の個数 の個数。
- の倍数は を2個持つので二重に数える。
- 。
よくある間違い
- 「 の倍数の個数」を数えて 個と答える( を作るのは因数 の組。 のような数も 個ずつ寄与する)。
- が を 個持つことを忘れ、 個と答える。
- 念のためにと因数 の個数( 個)まで正確に数えて時間を使う(「偶数だけでも 個 」の一言で の方が多いことは十分)。