C++で指定されたGCD値と一致する部分集合の個数を数える方法

問題の概要

正の整数を含む配列 arr と、GCD（最大公約数）の値を格納した配列 GCD[] が与えられます。この問題の目標は、arr[] の要素から構成されるすべての部分集合のうち、そのGCDが GCD[] に指定された値と一致するものの個数を求めることです。

入力例と出力例

例1

入力:

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

出力:

指定されたGCD値と一致する部分集合の個数: 1 2 2

説明:

• GCDが2となる部分集合は [10, 6] です。
• GCDが3となる部分集合は [3] と [6, 3] です。
• GCDが5となる部分集合は [5] と [10, 5] です。

例2

入力:

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

出力:

指定されたGCD値と一致する部分集合の個数: 1 2 0

説明:

• GCDが2となる部分集合は [10, 8] です。
• GCDが7となる部分集合は [7] と [21, 7] です。
• GCDが5となる部分集合は存在しないため、個数は0となります。

解法のアプローチ

このアプローチでは、unordered_map<int, int> 型のマップ um_1 を使って arr[] の各要素の出現頻度を記録し、同じく unordered_map である um_2 を使って「指定されたGCD値を持つ部分集合の個数」を保存します。まず arr[] の要素の中から最大値を count として取得します。その後、i = count から i ≥ 1 まで降順にループを回し、現在のGCD候補 i に対する部分集合の個数を求めていきます。

具体的には、um_1 に存在する i の倍数の個数を数えます。i の倍数の総数が total であるとき、GCDがちょうど i となる部分集合の個数は「2^total − 1 − temp」として計算できます。ここで temp は、GCDが i より大きい（i とは異なる）部分集合の個数です。大きなGCD側から順に計算していくことで、temp を参照する時点で必要な値がすべて確定している点がこの手法のポイントです。

アルゴリズムの手順

1. 配列 arr[] と GCD[] を用意します。
2. 関数 subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD) は、両方の配列とその長さを受け取り、指定されたGCD値と一致する部分集合の個数を出力します。
3. 初期値として count を 0 に設定します。
4. for ループで arr[] を走査し、count を要素の最大値で更新するとともに、um_1[arr[i]]++ により各要素の出現頻度を記録します。
5. i = count から i ≥ 1 までのループでは、total を「i の倍数の出現頻度の合計」、temp を 0（GCDが i より大きい部分集合の個数）として初期化します。
6. 続いて j = 2 から j × i ≤ count まで走査し、total に um_1[j×i] を加算し、temp に um_2[j×i] を加算します。
7. 両方のループが完了したら、um_2[i] = (1 << total) − 1 − temp を設定します。
8. 最後に、クエリごとの結果 um_2[GCD[i]] を出力します。

C++による実装例

#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

出力の解説

配列 arr = {9, 6, 2} の場合を確認してみましょう。GCDが2となる部分集合は [2] と [6, 2] の2つ、GCDが3となる部分集合は [9, 6] のみで1つです。したがって、クエリ GCD[] = {2, 3} に対する答えは「2 1」となります。

計算量について

外側のループは最大値 count 回、内側のループは各 i について count / i 回実行されるため、全体の時間計算量は調和級数の性質により O(N log N) 程度に収まります（N は配列の最大値）。すべての部分集合を列挙する指数時間の手法と比べ、非常に効率的なアプローチだと言えるでしょう。