Đếm số tập con của tập hợp có GCD bằng số cho trước trong C++

Cho một mảng arr chứa các số dương và một mảng GCD[] chứa các giá trị gcd. Mục tiêu là tìm số lượng tập con của các phần tử của arr[] có giá trị gcd như cho trong GCD[].

Ví dụ

Đầu vào

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

Đầu ra

Số tập con có GCD bằng số cho trước là: 1 2 2

Giải thích

Các tập con với GCD bằng 2 là [10, 6]. Tập con với GCD bằng 3 là [3], [6,3]. Tập con với GCD bằng 5 là [5], [10, 5]

Đầu vào

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

Đầu ra

Số tập con có GCD bằng số cho trước là: 1 2 0

Giải thích

Các tập con với GCD bằng 2 là [10, 8]. Tập con với GCD bằng 7 là [7], [21,7]. Không có tập con nào với GCD bằng 5.

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ tạo một unordered_map<int, int> um_1 để lưu tần suất các phần tử của arr[] và bản đồ tương tự um_2 để lưu số lượng tập con với gcd cho trước. Lấy giá trị lớn nhất trong các phần tử của arr[] làm count. Bây giờ chạy vòng lặp từ i=count đến i>=1 và tìm số lượng tập con cho gcd hiện tại. Để làm điều này, chúng ta sẽ đếm số bội số của i trong um_1. Nếu số bội số của i là total thì số tập con với gcd i là 2^total - 1 - temp. Trong đó temp là số tập con có gcd lớn hơn i nhưng không bằng i.

Nhận hai mảng cho arr[] và GCD[].
Hàm subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD) nhận cả hai mảng và độ dài của chúng và trả về số lượng tập con của tập hợp có GCD bằng số cho trước.
Khởi tạo biến đếm ban đầu là 0.
Duyệt arr[] bằng vòng lặp for, tìm và cập nhật count là giá trị tối đa và cập nhật um_1 với tần suất bằng um_1[arr[i]]++.
Sử dụng vòng lặp for từ i=count đến i>=1, lấy total là tổng tần suất của các bội số của i và temp=0 là số tập con có gcd lớn hơn i nhưng không bằng i.
Duyệt lại từ j=2 đến j*i <= count, cộng um_1[j*i] vào total và cộng um_2[j*i] vào temp.
Sau khi kết thúc cả hai vòng lặp for, đặt um_2[i] = (1<<total) - 1 - temp.
In um_2[GCD[i]] cho mảng kết quả có số lượng tập con với GCD cho trước.

Ví dụ mã

#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 << "Số tập con có GCD bằng số cho trước là: ";
    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;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số tập con có GCD bằng số cho trước là: 2 1