สร้าง Array ที่ GCD ของทุก Subset อยู่ในเซตที่กำหนด ในภาษา C

กำหนดเซตตัวเลข N ตัว ต้องสร้าง array ใหม่ ที่ GCD ของทุก subset อยู่ในเซตเดิม และความยาว array ใหม่ ≤ 3N

วิธีแก้

1. เรียงลำดับเซต
2. หา GCD ของทุกตัวในเซต
3. ถ้า GCD == ค่าต่ำสุดของเซต → สร้าง array โดยวาง GCD ระหว่างทุกคู่
4. เช่น {2,4,6,12} → GCD=2 (เท่ากับค่าต่ำสุด) → {2,2,4,2,6,2,12}

โค้ดตัวอย่าง (C++)

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

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

int getGCD(vector<int> arr) {
    int res = arr[0];
    for (int x : arr) res = gcd(res, x);
    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 << "No array can be built";
    }
}

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

ผลลัพธ์

2 2 4 2 6 2 12