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

Cho mảng A[] kích thước n. Xây dựng mảng B[] kích thước n+1 sao cho GCD(B[i], B[i+1]) = A[i]. Nếu nhiều nghiệm, chọn nghiệm có tổng nhỏ nhất.

Ví dụ: A = [1,2,3] → B = [1,2,6,3].

Giải pháp

• B[0] = A[0].
• Với i từ 0 đến n-2: B[i+1] = LCM(A[i], A[i+1]) (bội chung nhỏ nhất). Điều này đảm bảo GCD(B[i], B[i+1]) = A[i] và B[i+1] nhỏ nhất có thể.
• B[n] = A[n-1].

Ví dụ minh họa (C++)

#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 << "Mang xay dung: ";
    gcdArray(A, n);
    return 0;
}

Kết quả

Mang xay dung: 1 2 6 3