C++で指定された配列内の連続する要素のGCDから配列を構築します

n個の要素を持つ配列A[]があるとします。 B[i]とB[i+1]のGCDがA[i]であるように、サイズがn+1である別の配列B[]を見つける必要があります。複数のソリューションがある場合は、配列の合計が最小であるソリューションの1つを出力します。したがって、A =[1、2、3]の場合、出力は[1、2、6、3]

AにKと言う要素が1つしかない場合、B =[K、K]。したがって、B[0]はA[0]になります。ここで、インデックスiまで完了したと考えてください。これで、インデックスiがすでに処理され、B [i+1]が計算されています。ここで、B [i+1]およびB[i+ 2] =A [i + 1]のGCD、次にB [i+2]およびB[i+ 3] =A [i+2]のGCDです。したがって、B [i + 2]> =A [i + 1]、A [i+2]のLCM。最小の合計が必要なので、B [i + 2]の最小値を取得する必要があるため、B [i + 2] – A [i+2]とA[i+ 3]

例

#include <iostream>
#include <algorithm>
using namespace std;
int getLCM(int a, int b) {
   return (a * b) / __gcd(a, 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