C++で n! mod (k^x) = 0 となる最大の x を求める方法

2つの整数 n と k が与えられたとき、n! mod (k^x) = 0 を満たす最大の x の値を求める問題を考えます。例えば n = 5、k = 2 の場合、答えは 3 になります。これは n! = 120 であり、x の各値に対する剰余を計算すると次のようになるためです。

120 mod 2^0 = 0、120 mod 2^1 = 0、120 mod 2^2 = 0、120 mod 2^3 = 0、120 mod 2^4 = 8、120 mod 2^5 = 24、120 mod 2^6 = 56、120 mod 2^7 = 120

剰余が 0 となる最大の x は 3 であるため、出力は 3 となります。

解法のアプローチ

この問題を効率的に解くには、以下の手順に従います。

• k の平方根を計算し、変数 m に格納する
• i を 2 から m までループさせ、以下の処理を行う
  • i が m に達したら、i に k の値を代入する
  • k が i で割り切れる間、k を i で割り続ける
  • n までの範囲でループを実行し、その商を変数 u に加算する
  • 各ループの後に、結果の最小値を保存する

このアルゴリズムの本質は、k を素因数分解し、各素因数 p について「n! に含まれる p の個数」を「k に含まれる p の指数」で割った値の最小値を求める点にあります。n! に含まれる素因数の個数は、ルジャンドルの公式を用いることで効率的に計算できます。

サンプルコード

#include <iostream>
#include <cmath>
using namespace std;
int calculateMaxX(int n, int k) {
    int result = n, v, u;
    int m = sqrt(k) + 1;
    for (int i = 2; i <= m && k > 1; i++) {
        if (i == m) {
            i = k;
        }
        for (u = v = 0; k % i == 0; v++) {
            k /= i;
        }
        if (v > 0) {
            int t = n;
            while (t > 0) {
                t /= i;
                u += t;
            }
            result = min(result, u / v);
        }
    }
    return result;
}
int main() {
    int n = 5;
    int k = 2;
    cout << "Maximum value of x is: " << calculateMaxX(n, k);
}

出力結果

Maximum value of x is: 3

このプログラムの計算量は、k の素因数分解に O(√k)、各素因数に対するルジャンドルの公式の適用に O(log n) しかかからないため、大きな n や k が与えられた場合でも高速に動作します。