n개의 요소가 있는 배열 A[]가 있다고 가정합니다. B[i]와 B[i + 1]의 GCD가 A[i]가 되도록 크기가 n+1인 다른 배열 B[]를 찾아야 합니다. 여러 솔루션이 있는 경우 배열 합이 최소인 솔루션 중 하나를 인쇄하십시오. 따라서 A =[1, 2, 3]이면 출력은 [1, 2, 6, 3]
이 됩니다.A에 K라는 요소가 하나만 있으면 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]의 GCD =A[i + 2]. 따라서 B[i + 2]>=A[i + 1], A[i + 2]의 LCM입니다. 최소 합을 원하므로 B[i + 2]의 최소값을 원하므로 B[i + 2] – A[i + 2] 및 A[i + 3]의 LCM
예시
#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