Tìm các số gốc từ gcd () mọi cặp trong C ++

Khái niệm

Đối với một mảng mảng đã cho [] chứa GCD của mọi cặp phần tử có thể có của một mảng khác, nhiệm vụ của chúng ta là xác định các số ban đầu được sử dụng để tính toán mảng GCD.

Đầu vào

array[] = {6, 1, 1, 13}

Đầu ra

13 6
gcd(13, 13) = 13
gcd(13, 6) = 1
gcd(6, 13) = 1
gcd(6, 6) = 6

Đầu vào

arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}

Đầu ra

13 11 8 6 6

Phương pháp

• Lúc đầu, hãy sắp xếp mảng theo thứ tự giảm dần.

• Phần tử lớn nhất sẽ luôn là một trong các số ban đầu. Giữ nguyên số đó và xóa nó khỏi mảng.

• Tính GCD của phần tử đã thực hiện ở bước trước với phần tử hiện tại bắt đầu từ phần tử lớn nhất và loại bỏ giá trị GCD khỏi mảng đã cho.

Ví dụ

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Shows utility function to print
// the contents of an array
void printArr(int array[], int n1){
   for (int i = 0; i < n1; i++)
      cout << array[i] << " ";
}
// Shows function to determine the required numbers
void findNumbers(int array[], int n1){
   // Used to sort array in decreasing order
   sort(array, array + n1, greater<int>());
   int freq1[array[0] + 1] = { 0 };
   // Here, count frequency of each element
   for (int i = 0; i < n1; i++)
      freq1[array[i]]++;
   // Shows size of the resultant array
   int size1 = sqrt(n1);
   int brr1[size1] = { 0 }, x1, l1 = 0;
   for (int i = 0; i < n1; i++) {
      if (freq1[array[i]] > 0) {
         // Here, store the highest element in
         // the resultant array
         brr1[l1] = array[i];
         //Used to decrement the frequency of that element
         freq1[brr1[l1]]--;
         l1++;
         for (int j = 0; j < l1; j++) {
            if (i != j) {
               // Calculate GCD
               x1 = __gcd(array[i], brr1[j]);
               // Decrement GCD value by 2
               freq1[x1] -= 2;
            }
         }
      }
   }
   printArr(brr1, size1);
}
// Driver code
int main(){
   /* int array[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}; */
   int array[] = { 6, 1, 1, 13};
   int n1 = sizeof(array) / sizeof(array[0]);
   findNumbers(array, n1);
   return 0;
}

Đầu ra

13 6