C++で階乗に末尾のゼロが少なくともY個含まれる最小の数Xを求める方法

この記事では、「X!（Xの階乗）の末尾に少なくともY個のゼロが含まれるような最小の数Xを求める」という問題を取り上げます。例えば、Y = 2の場合、答えはX = 10です。10! = 3,628,800であり、末尾にちょうど2個のゼロが含まれているためです。

解法の考え方：二分探索

この問題は二分探索（バイナリサーチ）を使うことで効率的に解けます。鍵となるのは次の事実です。

N!の末尾のゼロの個数 ＝ N!に含まれる約数5の個数

末尾のゼロは10 = 2 × 5の積によって生じます。階乗の中では2の個数が常に5の個数より多いため、5が何回現れるかを数えればよいことになります。N!に含まれる5の個数は、ルジャンドルの公式に基づき次のように計算できます。

count = ⌊N/5⌋ + ⌊N/25⌋ + ⌊N/125⌋ + …

また、答えとなるXは必ず[0, 5×Y]の範囲内に存在するため、この範囲で二分探索を行います。

C++による実装例

#include<iostream>
using namespace std;
int factorCount(int n, int X) {
    if (X < n)
        return 0;
    return (X / n + factorCount(n, X / n));
}
int findX(int Y) {
    int left = 0, right = 5 * Y;
    int N = 0;
    while (left <= right) {
        int mid = (right + left) / 2;
        if (factorCount(5, mid) < Y) {
            left = mid + 1;
        } else {
            N = mid;
            right = mid - 1;
        }
    }
    return N;
}
int main() {
    int Y = 4;
    cout << "Smallest value of X: " << findX(Y);
}

コードの解説

factorCount関数

factorCount(n, X)は、X!に含まれるnの倍数の個数を再帰的に数える関数です。まずX/nで直接の倍数をカウントし、その商に対して再帰的に呼び出すことで、25や125といった5の累乗の寄与まで正確に数えています。

findX関数

findX(Y)が二分探索の本体です。探索範囲の左端を0、右端を5×Yに設定し、中央値midにおける末尾ゼロの個数がY未満であれば左端をmid + 1へ移動し、Y以上であれば答えの候補Nをmidに更新して右端をmid − 1へ移動させます。これにより、条件を満たす最小のXが求まります。

実行結果

Smallest value of X: 20

Y = 4の場合、出力は20になります。実際、20! = 2,432,902,008,176,640,000で末尾にちょうど4個のゼロが含まれ、19!ではゼロが3個しかないため、20が条件を満たす最小の数であることがわかります。

計算量

factorCountの計算量はO(log X)であり、二分探索と組み合わせた全体の計算量はO((log Y)²)程度に収まります。大きなYに対しても非常に高速に動作する効率的な手法です。