C++で指定された数に等しいGCDを持つセットのサブセットの数をカウントします

正の数を含む配列arとgcd値を含む配列GCD[]が与えられます。目標は、GCD[]で指定されたgcd値を持つarr[]の要素のサブセットの数を見つけることです。

例

入力

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.

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、arr[]の要素の頻度を格納するためのunordered_map um_1と、指定されたgcdのサブセットの数を格納するための同様のマップum_2を作成します。 arr[]の要素間の最大値をカウントとして使用します。ここで、i=countからi>=1までのループを実行し、現在のgcdのサブセットの数を見つけます。このために、um_1のiの倍数の数を数えます。 iの倍数の数が合計である場合、gcdiを持つサブセットの数はtotal2-1-tempです。ここで、tempは、gcdがiより大きいが、iと等しくないサブセットの数です。

• arr[]とGCD[]の2つの配列を取ります。

• 関数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を頻度で更新します。

• i=countからi>=1までのforループを使用して、合計をiの倍数の頻度の合計とし、temp=0をiより大きいがiと等しくないgcdを持つサブセットの数とします。

  >

• j=2からj*i <=countまで再度トラバースし、合計にum_1 [j * i]を追加し、tempにum_2 [j*i]を追加します。

• 両方のforループの終了後、um_2 [i] =（1 <を設定します。

• GCDが指定されたサブセットの数を持つ結果の配列の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;
}

出力

上記のコードを実行すると、次の出力が生成されます-

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