資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學用 C++ 統計 GCD 等於給定數字的集合子集個數
給定一個包含正數的陣列 arr 和一個包含 gcd 值的陣列 GCD[]。目標是找到 arr[] 元素的子集個數，其 gcd 值與 GCD[] 中給定的值相同。
例如
輸入
arr[] = {10, 5, 6, 3}, GCD[] = {2, 3, 5}輸出
Count of number of subsets of a set with GCD equal to a given number are: 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}輸出
Count of number of subsets of a set with GCD equal to a given number are: 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
為 arr[] 和 GCD[] 準備兩個陣列。
函式 `subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD)` 獲取這兩個陣列及其長度，並返回 GCD 等於給定數字的集合子集個數。
函式 `subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD)` 獲取這兩個陣列及其長度，並返回 GCD 等於給定數字的集合子集個數。
將初始計數設定為 0。
使用 for 迴圈遍歷 arr[]，找到最大值並更新計數，並使用 `um_1[arr[i]]++` 更新 `um_1` 中的頻率。
使用 for 迴圈從 i=count 到 i>=1，將 total 作為 i 的倍數頻率之和，並將 temp=0 作為 gcd 大於 i 但不等於 i 的子集個數。
再次從 j=2 到 j*i<=count 迴圈，將 `um_1[j*i]` 加到 total 中，並將 `um_2[j*i]` 加到 temp 中。
兩個 for 迴圈結束後，設定 `um_2[i] = (1<
列印 `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<<"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;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of number of subsets of a set with GCD equal to a given number are: 2 1
268 次瀏覽
