C++ですべての部分配列から最小のLCMとGCDを求める方法

サイズNの正の整数からなる配列 arr が与えられたとき、考えられるすべての部分配列の中で最小のLCM(最小公倍数)とGCD(最大公約数)を求める問題を考えてみましょう。例えば、配列が {2, 66, 14, 521} である場合、最小のLCMは 2、最小のGCDは 1 となります。

解き方のアプローチ

この問題は貪欲法(グリーディーアプローチ)を用いて効率的に解くことができます。ポイントは次の2点です。

• 部分配列に含まれる要素数を減らすほど、LCMは小さくなる傾向があります。
• 逆に、部分配列のサイズを大きくするほど、GCDは小さくなります。

したがって、求めるべき最小のLCMは「配列内の最小の要素」(単一要素からなる部分配列)となり、最小のGCDは「配列全体のすべての要素のGCD」となります。

C++による実装例

#include <iostream>
#include <algorithm>
using namespace std;
int minimum_gcd(int arr[], int n) {
    int GCD = 0;
    for (int i = 0; i < n; i++)
    GCD = __gcd(GCD, arr[i]);
    return GCD;
}
int minimum_lcm(int arr[], int n) {
    int LCM = arr[0];
    for (int i = 1; i < n; i++)
    LCM = min(LCM, arr[i]);
    return LCM;
}
int main() {
    int arr[] = { 2, 66, 14, 521 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "LCM: " << minimum_lcm(arr, n) << ", GCD: " << minimum_gcd(arr, n);
}

実行結果

LCM: 2, GCD: 1

このように、minimum_lcm 関数では配列を走査して最小値を求め、minimum_gcd 関数ではすべての要素を順番にGCD計算することで答えを得られます。どちらの処理もO(N)の計算量で実行できるため、非常に効率的な解法といえます。