หาตัวเลขต้นฉบับจาก gcd() ของทุกคู่ใน C++

แนวคิด

สำหรับอาร์เรย์ array[] ที่มี GCD ของทุกคู่ที่เป็นไปได้ของอีกอาร์เรย์หนึ่ง ภารกิจคือหาตัวเลขต้นฉบับที่ใช้คำนวณ GCD array

อินพุต

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;

// ฟังก์ชันพิมพ์อาร์เรย์
void printArr(int array[], int n1) {
    for (int i = 0; i < n1; i++)
        cout << array[i] << " ";
}

// ฟังก์ชันหาตัวเลขที่ต้องการ
void findNumbers(int array[], int n1) {
    // เรียงอาร์เรย์จากมากไปน้อย
    sort(array, array + n1, greater<int>());
    int freq1[array[0] + 1] = {0};
    
    // นับความถี่ของแต่ละสมาชิก
    for (int i = 0; i < n1; i++)
        freq1[array[i]]++;
    
    // ขนาดของอาร์เรย์ผลลัพธ์
    int size1 = sqrt(n1);
    int brr1[size1] = {0}, x1, l1 = 0;
    
    for (int i = 0; i < n1; i++) {
        if (freq1[array[i]] > 0) {
            // เก็บสมาชิกมากที่สุดในอาร์เรย์ผลลัพธ์
            brr1[l1] = array[i];
            // ลดความถี่ของสมาชิกนั้น
            freq1[brr1[l1]]--;
            l1++;
            
            for (int j = 0; j < l1; j++) {
                if (i != j) {
                    // คำนวณ GCD
                    x1 = __gcd(array[i], brr1[j]);
                    // ลดความถี่ GCD ลง 2
                    freq1[x1] -= 2;
                }
            }
        }
    }
    printArr(brr1, size1);
}

// Driver code
int main() {
    int array[] = {6, 1, 1, 13};
    int n1 = sizeof(array) / sizeof(array[0]);
    findNumbers(array, n1);
    return 0;
}

ผลลัพธ์

13 6