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

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

入力 : N = 7
出力 : 1
説明 : fact(7) = 5040（10進数）で、16進数では13B0となり、末尾のゼロは1個です。

入力 : N = 11
出力 : 2
説明 : fact(11) = 39916800（10進数）で、16進数では2611500となり、末尾のゼロは2個です。

10進数から16進数への変換のおさらい

まず、任意の10進数を別の基数へ変換する手順をおさらいしましょう。ここでは、(5040)₁₀ を16進数に変換する例を取り上げます。

具体的には、数値を16で割り、その余りを記録します。これを商が0になるまで繰り返し、最後に余りを逆順に並べたものが16進数表現になります。

この変換過程で現れる末尾のゼロは、「16で割ったときに余りが0になる」回数と一致します。

実際、5040は 16 × 45 × 7 と因数分解できます。つまり、16は5040をちょうど1回割り切ることができ、これが末尾のゼロ1個に対応します。この性質を利用すれば、巨大な階乗の値を実際に計算しなくても、末尾のゼロの個数を求められます。

解法のアプローチ

ここで重要なのは、16 = 2⁴ という事実です。N!に含まれる素因数2の個数（最大の冪）を求め、それを4で割れば、16で割り切れる回数、すなわち16進数表現における末尾のゼロの個数が分かります。

N!に含まれる素因数pの個数を求める手法は「ルジャンドルの公式」として知られており、次の式で表されます。

E_p(N!) = ⌊N/p⌋ + ⌊N/p²⌋ + ⌊N/p³⌋ + …

この公式を使えば、階乗の値を直接計算することなく、非常に効率的に答えを導き出せます。

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

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

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

int main () {
    int n = 11;
    long long int count = 0;
    long long int value, power = 2;
    long long int result;

    do{
        value = n / power;
        count += value;
        power *= 2;
    }
    while (value != 0);

    // countには2の最大の冪が格納される
    result = count / 4;
    cout << "Number of trailing zeroes in base 16 representation of N : " << result;
}

出力

Number of trailing zeroes in base 16 representation of N: 2

コードの解説

• 変数powerを2で初期化しています。これは、N!に含まれる2の最大の冪を計算する必要があるためです。
• do-whileループの中でルジャンドルの公式を実装しています。nをpower（初期値は2）で割った商をvalueとしてcountに加算し、powerを毎回2倍していきます。
• ループ終了後、countには2の最大の冪が格納されているため、それを4で割ることで16の最大の冪（＝末尾のゼロの個数）を求めています。
• 最後に結果を出力して処理を終了します。

まとめ

この記事では、階乗Nの16進数表現における末尾のゼロの個数を求める問題を、ルジャンドルの公式を活用して解決しました。あわせて、同じ問題を解くC++コードも紹介しました。このアルゴリズムはJava、C、Pythonなど、他のプログラミング言語でも簡単に実装できます。本記事が皆さんのお役に立てば幸いです。