C++で階乗の末尾のゼロの個数を求める効率的なアルゴリズム

階乗の末尾のゼロの個数を求めるには

この記事では、任意の整数 n の階乗(n!)の結果に含まれる「末尾のゼロ」の個数を効率的に求める方法を解説します。例えば、n = 5 のとき 5! = 120 なので末尾のゼロは 1 個、20! = 2432902008176640000 なので末尾のゼロは 4 個になります。

素朴な方法の問題点

最も単純なアプローチは、階乗の値を実際に計算してからゼロの個数を数えることです。しかし、n が大きくなると階乗の値は爆発的に増大し、int 型や long long 型でもすぐにオーバーフローしてしまうため、この方法は実用性がありません。

そこで、数学的な性質を利用した別のアプローチを用います。階乗の末尾にゼロが現れるのは、素因数分解したときに 2 と 5 がペアで含まれる場合です。つまり、2 と 5 の個数を数えれば答えが求まります。さらに、n! の素因数分解では 2 の個数が必ず 5 の個数より多くなるため、5 の個数だけを数えれば十分です。

計算式

末尾のゼロの数 = n! の素因数に含まれる 5 の個数

したがって、末尾のゼロの数は次の式で表せます。

⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …

この式の各項は、5 の倍数・25 の倍数(5 を 2 個含む)・125 の倍数(5 を 3 個含む)…に対応しています。n を 5 のべき乗で順に割り、その商(切り捨て)をすべて足し合わせることで答えが得られます。

アルゴリズムの手順

• count を 0 に初期化する
• i = 5 から開始し、n / i ≥ 1 を満たす間、i を 5 倍しながら繰り返す
  • count に n / i を加算する
• count を返す

C++での実装例

#include <iostream>
using namespace std;

int countTrailingZeros(int n) {
    int count = 0;
    for (int i = 5; n / i >= 1; i *= 5)
        count += n / i;
    return count;
}

int main() {
    int n = 20;
    cout << "末尾のゼロの個数: " << countTrailingZeros(n) << endl;
    return 0;
}

実行結果

入力:n = 20

末尾のゼロの個数: 4

計算量の評価

このアルゴリズムの計算量は O(log n) です。ループが 1 回回るごとに i が 5 倍になるため、n がどれほど大きくても反復回数は log₅ n 回程度に収まります。例えば n = 10¹⁸ という巨大な値でも、わずか 25 回程度の反復で答えが求まります。

まとめ

階乗を直接計算せずに素因数 5 の出現回数を数えることで、大きな n に対してもオーバーフローの心配なく末尾のゼロの個数を求められます。競技プログラミングでも頻出のテクニックなので、ぜひマスターしておきましょう。