Mảng có GCD thuộc tập con nào của nó thuộc mảng đã cho?

Ở đây chúng ta sẽ thấy một vấn đề thú vị. Có một tập hợp gồm N phần tử. Chúng ta phải tạo một mảng sao cho GCD của bất kỳ tập con nào của mảng đó nằm trong tập hợp các phần tử đã cho. Và một hạn chế khác là mảng được tạo không được dài hơn ba lần chiều dài của tập GCD. Ví dụ:nếu có 4 số {2, 4, 6, 12}, thì một mảng sẽ là {2, 2, 4, 2, 6, 2, 12}

Để giải quyết vấn đề này, đầu tiên chúng ta phải sắp xếp danh sách, sau đó nếu GCD giống với phần tử tối thiểu của tập hợp đã cho, thì tạo mảng chỉ bằng cách đặt GCD giữa mỗi phần tử. Nếu không, không có mảng nào có thể được tạo.

Thuật toán

createArray (arr, n)

Begin
   answer := empty array
   gcd := gcd of array arr
   if gcd is same as the min element of arr, then
      for each element e in arr, do
         append gcd into answer
         append e into answer
      done
      display answer
   else
      array cannot be formed
   end if
End

Ví dụ

#include<iostream>
#include<vector>
#include<set>
using namespace std;
int gcd(int a, int b) {
   if (a == 0)
      return b;
   return gcd(b % a, a);
}
int getGCDofArray(vector<int> arr) {
   int result = arr[0];
   for (int i = 1; i < arr.size(); i++)
      result = gcd(arr[i], result);
   return result;
}
void generateArray(vector<int> arr) {
   vector<int> answer;
   int GCD_of_array = getGCDofArray(arr);
   if(GCD_of_array == arr[0]) { //if gcd is same as minimum element
      answer.push_back(arr[0]);
      for(int i = 1; i < arr.size(); i++) { //push min before each
         element
         answer.push_back(arr[0]);
         answer.push_back(arr[i]);
      }
      for (int i = 0; i < answer.size(); i++)
      cout << answer[i] << " ";
   }
   else
   cout << "No array can be build";
}
int main() {
   int n = 4;
   int data[]= {2, 4, 6, 12};
   set<int> GCD(data, data + n);
   vector<int> arr;
   set<int>::iterator it;
   for(it = GCD.begin(); it!= GCD.end(); ++it)
      arr.push_back(*it);
   generateArray(arr);
}

Đầu ra

2 2 4 2 6 2 12