C++でnの階乗(n!)の末尾ゼロの個数を求める方法

問題概要

整数nが与えられたとき、n!(nの階乗)の末尾に連続して並ぶゼロ(後続ゼロ)の個数を求めることを考えます。

例えば、入力が n = 20 の場合、20! = 2432902008176640000 となるため、末尾にはゼロが4個連続しており、出力は4になります。

解法の考え方

末尾のゼロの個数は、階乗の計算結果に含まれる「10」の個数で決まります。10 = 2 × 5 であるため、因数2と因数5のペアの数がそのままゼロの個数に対応します。そして階乗の中では、因数2は因数5よりも必ず多く現れるため、因数5の出現回数を数えるだけでよいことが分かります。

具体的には、以下の手順で求めます。

• count を 0 で初期化します。
• i = 5 から開始し、n / i ≥ 1 である間、i を5倍ずつ更新しながら繰り返します。
• 各ループで count に n / i を加算します。これにより、5の倍数・25の倍数・125の倍数…に含まれる5の個数がすべて数え上げられます。
• 最終的な count を返します。

C++での実装例

#include <iostream>
#include <cmath>
#define MAX 20
using namespace std;

int countTrailingZeros(int n) {
    int count = 0;

    for (int i = 5; n / i >= 1; i *= 5)
        count += n / i;

    return count;
}

main() {
    int n = 20;
    cout << "Number of trailing zeros: " << countTrailingZeros(n);
}

入力

20

出力

Number of trailing zeros: 4

計算量とポイント

このアルゴリズムの時間計算量は O(log₅ n) です。ループのたびに i が5倍になるため、反復回数はわずか log₅ n 回程度で済みます。

n! を実際に計算してから末尾のゼロを数える方法もありますが、階乗は極めて大きな数値に急成長するため、オーバーフローや多倍長演算の必要性といった問題が生じます。本手法のように約数の性質を利用して直接カウントするアプローチの方が、高速かつ実用的です。