C++で配列要素の階乗の最大公約数（GCD）を求める方法

N個の要素を持つ配列Aが与えられたとき、配列内のすべての要素の階乗の最大公約数（GCD）を求めることを考えます。例えば、配列の要素が {3, 4, 8, 6} の場合、各要素の階乗は 3! = 6、4! = 24、8! = 40320、6! = 720 となり、これらのGCDは 6 になります。

解法のポイント

ここで重要な数学的な性質があります。2つの数のGCDとは、両方の数を割り切る最大の数のことです。階乗の場合、小さい数の階乗は必ず大きい数の階乗を割り切ることができます。つまり、2つの階乗のGCDは、小さい方の数の階乗そのものになります。

例えば、3! と 5! のGCDを考えると、3! = 6 であり、5! = 120 = 6 × 20 なので、gcd(3!, 5!) = 3! = 6 となります。

この性質を利用すると、配列全体の階乗のGCDを求めるには、配列内の最小値を見つけ、その最小値の階乗を計算するだけで済みます。すべての要素の階乗を実際に計算する必要がないため、非常に効率的なアルゴリズムです。

C++での実装例

#include <iostream>
using namespace std;

// 階乗を再帰的に計算する関数
long fact(int n){
    if(n <= 1)
        return 1;
    return n * fact(n-1);
}

// 配列の最小値の階乗を返す関数
int gcd(int arr[], int n) {
    int min = arr[0];
    for (int i = 1; i < n; i++) {
        if(min > arr[i])
            min = arr[i];
    }
    return fact(min);
}

int main() {
    int arr[] = {3, 4, 8, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "GCD: " << gcd(arr, n);
}

実行結果

GCD: 6

コードの解説

このプログラムは以下の手順で動作します。

1. fact() 関数が再帰を使って引数 n の階乗を計算します。
2. gcd() 関数がループ処理で配列内の最小値を探索します。
3. 見つかった最小値に対して fact() を呼び出し、その結果をGCDとして返します。

計算量について

このアプローチの利点は計算量にあります。素朴にすべての要素の階乗を計算してGCDを求めると、大きな数の階乗計算でオーバーフローや時間の問題が発生します。しかし本手法では、O(N) の時間で最小値を見つけ、1回の階乗計算だけで済むため、非常に高速かつメモリ効率に優れています。