นับสับเซตที่มี GCD เท่ากับค่าที่กำหนดด้วย C++

ได้รับอาร์เรย์ arr ที่มีจำนวนบวก และอาร์เรย์ GCD[] ที่มีค่า GCD เป้าหมายคือหาจำนวนสับเซตของสมาชิกใน arr[] ที่มีค่า GCD ตามที่กำหนดใน GCD[]

ตัวอย่าง

Input

arr[] = {10, 5, 6, 3}, GCD[] = {2, 3, 5}

Output

Count of number of subsets of a set with GCD equal to a given number are: 1 2 2

Explanation

The subsets with GCD equal to 2 is [ 10, 6 ]. Subsets with GCD equal to 3 is [ 3 ], [ 6,3 ] Subsets with GCD equal to 5 is [ 5 ], [ 10, 5 ]

Input

arr[] = {10, 21, 7, 8}, GCD[] = {2, 7, 5}

Output

Count of number of subsets of a set with GCD equal to a given number are: 1 2 0

Explanation

The subsets with GCD equal to 2 is [ 10, 8 ]. Subsets with GCD equal to 7 is [ 7 ], [ 21,7 ] There are no subsets with GCD equal to 5.

วิธีการที่ใช้ในโปรแกรม

วิธีนี้สร้าง unordered_map<int, int> um_1 เก็บความถี่ของสมาชิกใน arr[] และ um_2 เก็บจำนวนสับเซตที่มี GCD ตามที่กำหนด หาค่าสูงสุดใน arr[] เป็น count วนลูปจาก i=count ถึง i>=1 หาจำนวนสับเซตสำหรับ GCD ปัจจุบัน โดยนับจำนวนเท่าของ i ใน um_1 ถ้าจำนวนเท่าคือ total จำนวนสับเซตที่มี GCD = i คือ 2^total - 1 - temp โดย temp คือจำนวนสับเซตที่มี GCD มากกว่า i แต่ไม่เท่ากับ i

• รับอาร์เรย์สองตัว arr[] และ GCD[]
• ฟังก์ชัน subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD) คืนค่าจำนวนสับเซตที่ GCD เท่ากับค่าที่กำหนด
• กำหนดจำนวนนับเริ่มต้นเป็น 0
• วนลูป arr[] หาค่าสูงสุด และอัปเดต um_1[arr[i]]++
• ลูปจาก i=count ถึง i>=1 เก็บ total = um_1[i] และ temp=0
• ลูปอีกชั้นจาก j=2 ถึง j*i <= count บวก um_1[j*i] เข้า total และ um_2[j*i] เข้า temp
• ตั้ง um_2[i] = (1<<total) - 1 - temp
• พิมพ์ um_2[GCD[i]] สำหรับอาร์เรย์ผลลัพธ์

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

void subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD){
    unordered_map<int, int> um_1, um_2;
    int count = 0;
    for (int i=0; i<size_arr; i++){
        count = max(count, arr[i]);
        um_1[arr[i]]++;
    }
    for (int i = count; i >=1; i--){
        int temp = 0;
        int total = um_1[i];
        for (int j = 2; j*i <= count; j++){
            total += um_1[j*i];
            temp += um_2[j*i];
        }
        um_2[i] = (1<<total) - 1 - temp;
    }
    cout << "Count of number of subsets of a set with GCD equal to a given number are: ";
    for (int i=0; i<size_GCD ; i++){
        cout << um_2[GCD[i]] << " ";
    }
}

int main(){
    int GCD[] = {2, 3};
    int arr[] = {9, 6, 2};
    int size_arr = sizeof(arr)/sizeof(arr[0]);
    int size_GCD = sizeof(GCD)/sizeof(GCD[0]);
    subset_GCD(arr, size_arr, GCD, size_GCD);
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of number of subsets of a set with GCD equal to a given number are: 2 1