计算C ++中GCD等于给定数的集合的子集数
给定一个包含正数的数组ar和一个包含gcd的数组GCD[]values.The目标是找到具有GCD[]中给定的gcd值的arr[]元素子集的数量。
例如
输入值
arr[] = {10, 5, 6, 3}, GCD[] = {2, 3, 5}输出结果GCD等于给定数的集合的子集数计数为： 1 2 2
说明
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 ]
输入值
arr[] = {10, 21, 7, 8}, GCD[] = {2, 7, 5}输出结果GCD等于给定数的集合的子集数计数为： 1 2 0
说明
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[]中元素的最大值作为计数。现在运行一个从i=count到i>=1的循环，找到当前gcd的子集数。为此，我们将计算um_1中i的倍数。如果i的倍数总数为g，那么具有gcdi的子集的总数为2-1temp。其中temp是gcd大于i但不等于i的子集的数量。
将两个数组用于arr[]和GCD[]。
函数subset_GCD（intarr[]，intsize_arr，intGCD[]，intsize_GCD）接受两个数组及其长度，并返回GCD等于给定数的集合的子集数的计数。
函数subset_GCD（intarr[]，intsize_arr，intGCD[]，intsize_GCD）接受两个数组及其长度，并返回GCD等于给定数的集合的子集数的计数。
将初始计数设为0。
使用for循环遍历arr[]并找到更新计数作为最大值，并使用um_1[arr[i]]++用频率更新um_1。
使用从i=count到i>=1的for循环，将总数作为i的倍数和temp=0的频率之和作为gcd大于i但不等于i的子集数。
再次从j=2遍历到j*i<=count，将um_1[j*i]添加到总计，并将um_2[j*i]添加到temp。
在两个for循环结束后，设置um_2[i]=（1<<total）−1−temp。
打印um_2[GCD[i]]以得到具有给定GCD子集数的结果数组。
示例
#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<<"GCD等于给定数的集合的子集数计数为： ";
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;
}输出结果如果我们运行上面的代码，它将生成以下输出-
GCD等于给定数的集合的子集数计数为： 2 1