C++의 모든 쌍에서 gcd()에서 원래 숫자 찾기

컨셉

다른 배열의 가능한 모든 요소 쌍의 GCD를 포함하는 주어진 배열 array[]와 관련하여 우리의 임무는 GCD 배열을 계산하는 데 사용되는 원래 숫자를 결정하는 것입니다.

입력

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

출력

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

입력

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}

출력

13 11 8 6 6

방법

• 먼저 배열을 내림차순으로 정렬합니다.

• 가장 큰 요소는 항상 원래 숫자 중 하나입니다. 해당 번호를 유지하고 어레이에서 삭제하십시오.

• 현재 요소가 가장 큰 것부터 시작하여 이전 단계에서 가져온 요소의 GCD를 계산하고 주어진 배열에서 GCD 값을 버립니다.

예시

// 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;
}

출력

13 6