Xây dựng một mảng từ GCD của các phần tử liên tiếp trong mảng đã cho trong C ++

Giả sử chúng ta có một mảng A [], với n phần tử. Chúng ta phải tìm một mảng B [] khác, có kích thước là n + 1, sao cho GCD của B [i] và B [i + 1] là A [i]. Nếu có nhiều giải pháp, thì in một trong số chúng có tổng mảng là nhỏ nhất. Vì vậy, nếu A =[1, 2, 3], thì đầu ra sẽ là [1, 2, 6, 3]

Khi A chỉ có một phần tử nói K, thì B =[K, K]. Vì vậy, B [0] sẽ là A [0]. Bây giờ hãy xem xét chúng ta đã hoàn thành chỉ mục i, vì vậy chúng ta đã xử lý chỉ số i và tính B [i + 1]. Bây giờ GCD của B [i + 1] và B [i + 2] =A [i + 1], sau đó GCD của B [i + 2] và B [i + 3] =A [i + 2]. Vậy B [i + 2]> =LCM của A [i + 1], A [i + 2]. Vì chúng ta muốn tổng nhỏ nhất, thì chúng ta muốn nhận giá trị nhỏ nhất của B [i + 2], do đó B [i + 2] - LCM của A [i + 2] và A [i + 3]

Ví dụ

#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);
}

Đầu ra

Constructed array: 1 2 6 3