C++で隣接要素のGCDが指定配列と一致する配列を構築する方法

問題の概要

n個の要素を持つ配列A[]が与えられたとき、サイズがn+1である別の配列B[]を構築することを考えます。ここで要求される条件は、B[i]とB[i+1]の最大公約数（GCD）がA[i]と一致することです。条件を満たす解が複数存在する場合は、配列の要素の合計値が最小となるものを一つ出力します。

例えば、A = [1, 2, 3] の場合、出力は [1, 2, 6, 3] となります。実際に確認すると、GCD(1, 2) = 1、GCD(2, 6) = 2、GCD(6, 3) = 3 となり、すべての条件を満たしています。

アルゴリズムの考え方

まず、Aに要素が1つだけある場合（その値をKとする）を考えます。このとき、B = [K, K] となり、B[0]はA[0]と等しくなります。

次に、インデックスiまでの処理が完了し、B[i+1]まで計算済みである状況を想定します。このとき、以下の関係が成り立ちます。

• B[i+1]とB[i+2]のGCD = A[i+1]
• B[i+2]とB[i+3]のGCD = A[i+2]

この条件から、B[i+2]は必ずA[i+1]とA[i+2]の最小公倍数（LCM）以上の値になります。配列の合計を最小化したいので、B[i+2]には取り得る最小の値、すなわちA[i+1]とA[i+2]の最小公倍数を採用するのが最適です。

以上をまとめると、構築ルールは次のようになります。

• 先頭の要素：B[0] = A[0]
• 末尾の要素：B[n] = A[n-1]
• 中間の要素：B[i+1] = LCM(A[i], A[i+1])

C++による実装例

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

// 最大公約数を使って最小公倍数を求める
int getLCM(int a, int b) {
    return (a * b) / __gcd(a, b);
}

// 条件を満たす配列Bを構築して出力する
void gcdArray(int A[], int n) {
    cout << A[0] << " ";
    for (int i = 0; i < n - 1; i++)
        cout << getLCM(A[i], A[i + 1]) << " ";
    cout << A[n - 1];
}

int main() {
    int A[] = { 1, 2, 3 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Constructed array: ";
    gcdArray(A, n);
}

出力結果

Constructed array: 1 2 6 3

計算量について

このアルゴリズムは配列を一度走査するだけで済むため、時間計算量はO(n)、空間計算量も出力用の配列を除けばO(1)と非常に効率的です。各要素のLCM計算はユークリッドの互除法に基づく__gcd関数により高速に処理されます。