C++で解く！Nの階乗のB進表現における末尾ゼロの個数の求め方

はじめに

この記事では、与えられた数Nの階乗（N!）を基数Bで表したとき、末尾にいくつのゼロが連続するかを求める問題について詳しく解説します。

問題の例

入力 : N = 7、基数 = 2
出力 : 4
説明 : fact(7) = 5040（10進数）であり、2進数では「1001110110000」となるため、末尾にゼロが4個並びます。

入力 : N = 11、基数 = 5
出力 : 2
説明 : fact(11) = 39916800（10進数）であり、5進数では「40204314200」となるため、末尾にゼロが2個並びます。

基数変換のおさらい

まず、10進数から他の基数へ数値を変換する手順を確認しておきましょう。ここでは (5040)₁₀ を2進数に変換する例を取り上げます。

具体的には、数値を基数で順番に割っていき、そのたびに余りを記録します。それ以上割り切れなくなった時点で処理を終了し、記録した余りを逆順に並べたものが変換結果となります。

この例では、末尾にゼロが4個現れています。この末尾のゼロは、「2で割ったときの余りが0となった回数」、つまり2で割り切れた回数と一致します。

5040を素因数分解すると 2⁴ × 7¹ × 3² × 5¹ となります。これは、2が5040を余り0でちょうど4回割り切れることを意味し、末尾のゼロの個数とも一致しています。この性質を利用すれば、実際に基数変換を行わなくても末尾のゼロの個数を計算できるのです。

解法のアプローチ

ここまで見てきたように、求めるべきは「N!を割り切るBの最大のべき乗」です。たとえば基数B = 14の場合、14は14進数で「10」と表されるので (14)₁₀ = (10)₁₄ となり、末尾のゼロの個数はN!に含まれる14のべき乗の指数と一致します。この計算に用いられるのが、ルジャンドルの公式（Legendre's formula）として知られる有名な手法です。

上記アプローチのC++コード

以下のC++コードは、この問題を解くためにそのまま利用できます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

vector < pair < int, int >> primeFactorsofBase(int Base) {
    // 基数の素因数と、その素因数分解における出現回数を格納
    vector < pair < int, int >> factors;

    for (int i = 2; Base != 1; i++) {
        if (Base % i == 0) {
            int count = 0;
            while (Base % i == 0){
                Base = Base / i;
                count++;
            }
            factors.push_back(make_pair(i, count));
        }
    }
    return factors;
}

int main () {
    int N = 11, Base = 5;
    // 階乗Nを割り切る基数の最大のべき乗を求める
    vector < pair < int, int >> prime_factors;
    // primeFactorsofBase() 関数で素因数を求める
    prime_factors = primeFactorsofBase(Base);

    int result = INT_MAX;
    for (int i = 0; i < prime_factors.size(); i++) {
        // 各素因数について最小のべき乗を計算
        int count = 0;
        int r = prime_factors[i].first;
        while (r <= N){
            count += (N / r);
            r = r * prime_factors[i].first;
        }
        result = min(result, count / prime_factors[i].second);
    }
    // result に格納された末尾ゼロの個数を出力
    cout << "Number of trailing zeroes: " << result;
    return 0;
}

出力

Number of trailing zeroes: 2

コードの解説

• ベクター（vector）を使って、基数を割り切る最大のべき乗を求めます。
• 最大のべき乗を計算するために、primeFactorsofBase() 関数で基数を素因数分解し、すべての素因数をベクターに格納します。
• その後、基数の各素因数ごとにルジャンドルの公式でべき乗の指数を計算し、その中で最小の値を求めます。
• 最後に、求めた末尾ゼロの個数（result）を出力します。

まとめ

この記事では、Nの階乗のB進表現における末尾のゼロの個数を求める問題を、ルジャンドルの公式を用いて解決しました。あわせて、同じ問題を解くためのC++のコードも紹介しています。このコードはJava、C、Pythonなど、他のプログラミング言語でも同様のロジックで実装可能です。本記事が皆さまの学習の一助となれば幸いです。