配列の全ての要素(N個)の最大公約数(GCD)を求めるアルゴリズム
配列 A が与えられて、その全ての要素の最大公約数(GCD)を求めることを考えます。2つの最大公約数だけではなく、N個の要素の最大公約数を求めます。
例：
Input: A = {36, 12, 48}
Output: 12
アルゴリズム
N個の自然数の最大公約数：
- リスト {\(a_1, a_2, a_3,…, a_N\)} の要素数が 1 つになるまで以下を繰り返す
- リストから2つ選んで最大公約数 gcd を計算し、リストに加える
- 残った 1 つが全体の最大公約数
※ 複数の自然数の最大公約数を求める場合でも、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;
}