Tạo mảng GCD mọi tập con thuộc tập cho trước trong C

Cho tập N phần tử. Tạo mảng sao cho GCD của mọi tập con đều nằm trong tập gốc. Độ dài mảng ≤ 3N.

Ví dụ

Tập {2, 4, 6, 12} → Mảng: {2, 2, 4, 2, 6, 2, 12}

Điều kiện

GCD của tập gốc = phần tử nhỏ nhất. Khi đó chèn phần tử nhỏ nhất giữa các phần tử.

Chương trình

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
    return a == 0 ? b : gcd(b % a, a);
}

int getGCD(vector<int> arr) {
    int res = arr[0];
    for (int x : arr) res = gcd(x, res);
    return res;
}

void generateArray(vector<int> arr) {
    sort(arr.begin(), arr.end());
    int g = getGCD(arr);
    
    if (g == arr[0]) {
        vector<int> ans;
        ans.push_back(arr[0]);
        for (int i = 1; i < arr.size(); i++) {
            ans.push_back(arr[0]);
            ans.push_back(arr[i]);
        }
        for (int x : ans) cout << x << " ";
    } else {
        cout << "Khong the tao mang";
    }
}

int main() {
    vector<int> arr = {2, 4, 6, 12};
    generateArray(arr);
    return 0;
}

Kết quả

2 2 4 2 6 2 12