สร้างอาร์เรย์จาก GCD ขององค์ประกอบติดกันในอาร์เรย์ที่กำหนดใน C++

สมมติว่ามีอาร์เรย์ A[] ขนาด n องค์ประกอบ เราต้องหาอีกอาร์เรย์ B[] ขนาด n+1 ที่ทำให้ GCD ของ B[i] และ B[i+1] เท่ากับ A[i] ถ้ามีหลายคำตอบ ให้พิมพ์คำตอบที่ผลรวมอาร์เรย์น้อยที่สุด ดังนั้นถ้า A = [1, 2, 3] ผลลัพธ์คือ [1, 2, 6, 3]

เมื่อ A มีแค่ 1 องค์ประกอบ คือ K แล้ว B = [K, K] ดังนั้น B[0] = A[0] ตอนนี้พิจารณาว่าเราทำเสร็จแล้วถึง Index i หมายความว่าเราประมวลผล Index i แล้ว และคำนวณ B[i+1] ได้แล้ว ตอนนี้ GCD(B[i+1], B[i+2]) = A[i+1] แล้ว GCD(B[i+2], B[i+3]) = A[i+2] ดังนั้น B[i+2] ≥ LCM(A[i+1], A[i+2]) เนื่องจากเราต้องการผลรวมน้อยที่สุด เราจึงต้องการค่า B[i+2] น้อยที่สุด ดังนั้น B[i+2] = LCM(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