Cho một mảng ar, 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ố tập hợp con của các phần tử của arr [] có các giá trị gcd như đã cho trong GCD [].
Ví dụ
Đầu vào
arr[] = {10, 5, 6, 3}, GCD[] = {2, 3, 5} Đầu ra
Count of number of subsets of a set with GCD equal to a given number are: 1 2 2
Giải thích
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 ]
Đầu vào
arr[] = {10, 21, 7, 8}, GCD[] = {2, 7, 5} Đầu ra
Count of number of subsets of a set with GCD equal to a given number are: 1 2 0
Giải thích
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.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Trong cách tiếp cận này, chúng ta sẽ tạo một bản đồ không có thứ tự
-
Lấy hai mảng cho arr [] và GCD [].
-
Hàm subset_GCD (int arr [], int size_arr, int GCD [], int size_GCD) nhận cả mảng và độ dài của chúng và trả về số lượng các tập con của một tập hợp có GCD bằng một số nhất định.
-
Hàm subset_GCD (int arr [], int size_arr, int GCD [], int size_GCD) nhận cả mảng và độ dài của chúng và trả về số lượng các tập con của một tập hợp có GCD bằng một số nhất định.
-
Lấy số lượng ban đầu là 0.
-
Traverse arr [] bằng cách sử dụng vòng lặp for và tìm số bản cập nhật là giá trị lớn nhất và cập nhật um_1 với tần số bằng cách sử dụng um_1 [arr [i]] ++.
-
Sử dụng vòng lặp for từ i =count đến i> =1, lấy tổng là tổng tần số của 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.
-
Đảo ngược lại từ j =2 sang j * i <=count, thêm um_1 [j * i] vào tổng và thêm um_2 [j * i] vào tạm thời.
-
Sau khi kết thúc cả hai vòng lặp for, đặt um_2 [i] =(1 <
-
In ô_2 [GCD [i]] cho mảng kết quả có số lượng các tập con với GCD đã cho.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of number of subsets of a set with GCD equal to a given number are: 2 1