配列の全ての要素(N個)の最大公約数(GCD)を求めるアルゴリズム

2020年3月21日数学最大公約数,配列,結合則

配列 A が与えられて、その全ての要素の最大公約数(GCD)を求めることを考えます。2つの最大公約数だけではなく、N個の要素の最大公約数を求めます。

例:

Input: A = {36, 12, 48}
Output: 12

アルゴリズム

N個の自然数の最大公約数:

  1. リスト {\(a_1, a_2, a_3,…, a_N\)} の要素数が 1 つになるまで以下を繰り返す
    • リストから2つ選んで最大公約数 gcd を計算し、リストに加える
  2. 残った 1 つが全体の最大公約数

※ 複数の自然数の最大公約数を求める場合でも、2つずつ最大公約数を求めていけば、最終的に全ての自然数の最大公約数が求まります。

※ 2つの場合の最大公約数の求め方はこちらを参照

計算量

  • \(O(N \log( a’ ) )\) (\(a’\) は二番目に大きい数)

2つの最大公約数の計算を N-1 回繰り返すことになります。

C++での実装例

 ※ gcd はC++17 から標準ライブラリに追加されています。以下は C++14 での例です。

long long gcd(long long a, long long b) { // 2つの場合の最大公約数
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

long long gcd_vec(vector<long long> const &A) { // N個の要素に対する最大公約数
    int size = (int)A.size();
    long long ret = A[0];
    for (int i = 1; i < size; i++) {
        ret = gcd(ret, A[i]);
    }
    return ret;
}

練習問題