Paizaで階乗の末尾の 0 を数える問題に挑戦したら、まさかの“桁数オーバー事件”！
でも、冷静に考えたら意外とシンプルなルールに気づいて解決！
問題概要
- 整数 N が与えられる。
- N の階乗 N! の末尾に 0 がいくつ付くか求め、出力。
入力例：
100
出力例：
24
❌ NG例
const rl = require('readline').createInterface({ input: process.stdin });
rl.once('line', (input) => {
const N = Number(input);
// 階乗を計算（前回のコード）
let factorial = 1;
for (let i = 1; i <= N; i++) {
factorial *= i;
}
// 文字列化して、末尾の0を正規表現で取得
const zeroMatch = String(factorial).match(/0+$/);
// nullの場合は末尾に0がないから、カウントは0
const zeroCount = zeroMatch ? zeroMatch[0].length : 0;
console.log(zeroCount);
rl.close();
});
- 末尾の連続する 0 を
/0+$/で取得 -
.match()は、見つからないとnullになるから、
zeroMatch ?zeroMatch[0].length : 0で安全に出力
⚠️ 問題点 ：N! がとても大きくなる
例えば N=100 だと、
100! は 158桁もある巨大な整数になる。
JavaScript の Number型 は 約 16 桁までしか正確に表せない。
（64ビット浮動小数点数のため）
🤔 末尾0の仕組みを考えてみる
→末尾の 0 は「10 の倍数」がいくつ含まれているかで決まる！
末尾に0がつくのは、数字が10の倍数になっているときだよね。
10 = 2 × 5 だから、10を作るために必要な因数「2」と「5」を数えればいい！
でも、N! には 2 の因子がものすごく多いのに対して、5 の因子はずっと少ない。
例: 10! ：
10! = 1×2×3×…×10
5 は 5,10 など
2 は 2,4,6,8,10 などからたくさん出てくる
🔥 「5の倍数」で末尾0をカウント！
具体的には、N! に含まれる 5 の因子の数を数えるだけでOK！
でも注意！5の倍数だけじゃなくて、25（=5²）、125（=5³）…と、5の累乗が出てくる数も追加でカウントする必要がある。
例えば、N=100のときの5の因子の数を数える流れはこう。
1️⃣ まず「5の倍数の個数」を数える。
100/5 = 20（20個ある！）
2️⃣ 次に「25の倍数の個数」も考慮。
100/25 = 4（25は5×5だから、さらに1つ5が含まれる）
3️⃣ 125は100以下にないから、終了。
合計すると、20+4=24 で、末尾の0は24個になる。
最初に階乗を計算しなくても、こうやって5の因子の個数を足すだけで解決！
🔎 なぜ 25（5²）で割れるものも考慮するのか？
末尾ゼロを生む条件は「10 = 2×5」なので、N! に含まれる「5の数」を数えるんだけど…
N! には 5 の倍数だけでなく、25（=5²）、125（=5³） で割れる数 もある。
たとえば 25! には：
5 の倍数が 5, 10, 15, 20, 25 → 5の倍数は5回
25 は 5² なので、さらに1回カウントされる（5²は5が2回含まれるから）
✅OK例
そんな気づきから、最終的に書いて正解したコードがこちら。
const rl = require('readline').createInterface({input: process.stdin});
rl.once('line', (input) => {
const N = Number(input);
let count = 0;
for (let i = 5; i <= N; i *= 5) {
count += Math.floor(N / i);
}
console.log(count);
rl.close();
});
- 末尾の 0 は「10 の倍数」がいくつ含まれているかで決まる。
- 10 = 2 × 5 なので、N! に含まれる 5 の数 に注目すればいい。
- 5, 25, 125… の倍数ごとに加算
📝 気づきメモ
- 末尾0の数は「10の因子の数」だけど、2は多すぎるから「5の因子数」で決まる。
- 5, 25, 125…の累乗を考慮するのがポイント！
- JSの浮動小数点数の限界を意識して、計算の方針を変える必要がある。
🎯 まとめ
というわけで、Paizaの「階乗の末尾0」問題は、大きな数の階乗を直接計算しようとすると失敗するってことと、数の性質に注目するのが大事ってことを学んだ！数学チックな問題だった(´;ω;｀)