C++で配列内の最大GCDを持つペアを検索する方法

問題の概要

正の整数で構成される配列が与えられたとき、その中からGCD(最大公約数)が最大となる整数のペアを見つけるのがこの記事のテーマです。

例として、配列 A = {1, 2, 3, 4, 5} を考えてみましょう。この場合の出力は 2 になります。ペア (2, 4) のGCDが 2 であり、それ以外のどのペアのGCDも 2 未満にしかならないためです。

解法のアプローチ

この問題を効率的に解くには、各約数の出現回数を記録するカウント配列を活用します。全体の流れは次の通りです。

1. 配列内の各要素について約数をすべて列挙し、カウント配列に記録します。1つの要素の約数列挙には O(√arr[i]) の時間がかかります。
2. すべての要素の処理が完了したら、カウント配列を大きいインデックス側から小さいインデックスへ向かって走査します。
3. カウントが 2 以上になっている値が見つかった時点で、それは 2 つ以上の要素に共通する約数、すなわち最大のGCDだと判断できます。

C++による実装例

#include <iostream>
#include <cmath>
using namespace std;

int getMaxGCD(int arr[], int n) {
    int high = 0;
    for (int i = 0; i < n; i++)
        high = max(high, arr[i]);

    int divisors[high + 1] = { 0 }; // すべてのGCD候補を格納する配列

    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= sqrt(arr[i]); j++) {
            if (arr[i] % j == 0) {
                divisors[j]++;
                if (j != arr[i] / j)
                    divisors[arr[i] / j]++;
            }
        }
    }

    for (int i = high; i >= 1; i--)
        if (divisors[i] > 1)
            return i;
}

int main() {
    int arr[] = { 1, 2, 4, 8, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Max GCD: " << getMaxGCD(arr, n);
}

実行結果

Max GCD: 4

配列 {1, 2, 4, 8, 12} の場合、ペア (4, 8)、(4, 12)、(8, 12) のいずれもGCDが 4 となり、これが最大値です。

計算量の評価

N を配列の要素数、M を配列内の最大値とすると、約数の列挙に全体で O(N√M)、最大GCDの探索に O(M) かかるため、全体の時間計算量は O(N√M + M) となります。すべてのペアを総当たりで調べる O(N²) のアプローチと比べ、要素数が多い場合でも高速に動作するのが大きな利点です。