【C++】配列を互いに素な配列に変換するための最小挿入回数を求める方法

問題の概要

今回は、与えられた配列を互いに素な配列（コプライム配列）に変換するために必要な最小の挿入回数を求める、興味深い問題を取り上げます。互いに素な配列とは、隣り合う任意の2つの要素の最大公約数（GCD）が必ず1になる配列のことです。この記事では、必要な挿入回数に加えて、変換後の配列そのものも出力します。

例として、{5, 10, 20} という配列を考えてみましょう。この配列は隣接要素同士のGCDが5や10となるため、互いに素な配列ではありません。しかし、5と10の間、そして10と20の間にそれぞれ「1」を挿入すれば、{5, 1, 10, 1, 20} となり、すべての隣接ペアのGCDが1になります。

アルゴリズム

アプローチは非常にシンプルです。配列を先頭から順に走査し、隣接する2要素のGCDが1でない箇所を見つけたら、その間に「1」を挿入します。「1」と任意の整数のGCDは常に1であるため、この操作だけで必ず互いに素な配列を作ることができます。

makeCoPrime(arr, n):
begin
    count := 0
    for i in range 1 to n-1, do
        if gcd(arr[i], arr[i-1]) != 1, then
            count := count + 1
    done
    display count
    display arr[0]
    for i in range 1 to n-1, do
        if gcd(arr[i], arr[i-1]) != 1, then
            display 1
        display arr[i]
    done
end

C++による実装例

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

void makeCoPrime(int arr[], int n){
    int count = 0;
    // 挿入が必要な箇所をカウント
    for(int i = 1; i < n; i++){
        if(__gcd(arr[i], arr[i - 1]) != 1){
            count++;
        }
    }
    cout << "挿入回数: " << count << endl;
    // 必要に応じて1を挿入しながら配列を出力
    cout << arr[0] << " ";
    for(int i = 1; i < n; i++){
        if(__gcd(arr[i], arr[i - 1]) != 1){
            cout << 1 << " ";
        }
        cout << arr[i] << " ";
    }
}

int main() {
    int A[] = {2, 7, 28};
    int n = sizeof(A)/sizeof(A[0]);
    makeCoPrime(A, n);
}

実行結果

挿入回数: 1
2 7 1 28

解説

入力配列 {2, 7, 28} の場合、gcd(2, 7) = 1 なのでこのペアはそのままで問題ありませんが、gcd(7, 28) = 7 となるため、この間に「1」を1つ挿入する必要があります。したがって、挿入回数は1回、出力される配列は「2 7 1 28」となります。

このアルゴリズムは配列を1度走査するだけでよいため、時間計算量は O(n log M)（M は要素の最大値）、空間計算量は O(1) と非常に効率的です。また、挿入する値として「1」を選ぶことで、どのような整数の組み合わせに対しても確実にGCDを1にできる点がポイントです。