C++で配列のGCD（最大公約数）を1にする変換アルゴリズム

このチュートリアルでは、配列全体のGCD（最大公約数）が1になるように配列を変換するプログラムをC++で解説します。

問題の概要

ここでは、配列と正整数 k が与えられます。許される操作は「配列の要素を k で割る」ことだけで、この操作は各要素が k 未満になるまで何度でも繰り返し行えます。この操作のみを使って、すべての要素のGCDを1にできるかどうかを判定するのが課題です。

アプローチのポイント

鍵となるのは「k の素因数はすべて k 以下である」という性質です。要素を k で割って取り除けるのは k の素因数だけなので、k より大きい素因数はどれだけ操作を繰り返しても消すことができません。

したがって、次の手順で判定できます。

1. 配列全体のGCDを計算する。
2. そのGCDを素因数分解し、最大の素因数を求める。
3. 最大の素因数が k 以下であれば "Yes"（GCDを1にできる）、そうでなければ "No"。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
// 配列のGCDを計算する
int calculate_gcd(int* arr, int n){
    int gcd = arr[0];
    for (int i = 1; i < n; i++)
        gcd = __gcd(arr[i], gcd);
    return gcd;
}
// 操作が可能かどうかを判定する
bool convertGcd(int* arr, int n, int k){
    int gcd = calculate_gcd(arr, n);
    int max_prime = 1;
    for (int i = 2; i <= sqrt(gcd); i++) {
        while (gcd % i == 0) {
            gcd /= i;
            max_prime = max(max_prime, i);
        }
    }
    max_prime = max(max_prime, gcd);
    return (max_prime <= k);
}
int main(){
    int arr[] = { 10, 15, 30 };
    int k = 6;
    int n = sizeof(arr) / sizeof(arr[0]);
    if (convertGcd(arr, n, k) == true)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

出力

Yes

コードの解説

calculate_gcd 関数

標準ライブラリの __gcd を使い、配列の先頭要素を初期値として順番にGCDを更新していき、配列全体のGCDを求めます。

convertGcd 関数

まず配列全体のGCDを取得し、2から√GCDまで順に試し割りして素因数分解を行います。見つかった素因数のうち最大のものを max_prime として記録し、最後に残った商も候補として比較します。そして max_prime <= k が成り立てば true を返します。

main 関数

サンプルとして配列 {10, 15, 30} と k = 6 を使用しています。配列のGCDは5であり、その最大素因数は5で k = 6 以下のため、"Yes" が出力されます。

計算量

GCDの計算には O(n log max(arr))、素因数分解には O(√GCD) かかるため、全体の計算量は O(n log max(arr) + √GCD) となります。要素数や値が大きい場合でも効率的に動作する実装です。