C++で割り切れる関係にあるペア(i, j)の個数を数える方法

N個の要素を持つ配列 arr[] が与えられたとします。この記事の目的は、「arr[i] が arr[j] で割り切れる」または「arr[j] が arr[i] で割り切れる」という条件を満たし、かつ i != j である有効なインデックスのペア (i, j) の総数を求めることです。

これを実現するために、2重のforループを使って配列 arr[] を走査し、ペアごとに i != j のとき arr[i] % arr[j] == 0 または arr[j] % arr[i] == 0 が成り立つかどうかを確認します。条件が真であれば、ペアのカウントを1つ増やしていきます。

それでは、具体例を見ながら理解を深めましょう。

入力 − Arr[]= { 2,4,3,6 }、N=4

出力 − 有効なペアの個数 − 3

説明 − 有効なペアは以下の通りです。

Arr[0] & Arr[1] → (2,4) ここで 4%2==0、かつ 0!=1
Arr[0] & Arr[3] → (2,6) ここで 6%2==0、かつ 0!=3
Arr[2] & Arr[3] → (3,6) ここで 6%3==0、かつ 2!=3

入力 − Arr[]= { 2,5,7,9,11 }、N=5

出力 − 有効なペアの個数 − 0

説明 − どの要素も他の要素を割り切ることができないため、有効なペアは1つも存在しません。

プログラムで使用するアプローチ

• ランダムな値で初期化された整数型配列 Arr[] を用意します。

• Arr[] の長さを格納する変数 n を宣言します。

• 関数 countPairs(int arr[], int n) は、配列とその長さを引数として受け取り、条件を満たす有効なペアの個数を返します。

• 2つのforループを使って配列を走査し、ペアを構成する各要素を調べます。

• 外側のループは 0<=i<n-1 の範囲、内側のループは i<j<n の範囲で実行します。

• arr[i]%arr[j]==0 または arr[j]%arr[i]==0 であるかを判定し、いずれかの条件が真であればカウントを1増やします。

• すべてのループが完了した時点で、count には有効なペアの総数が格納されています。

• 最後に count を結果として返します。

なお、この方法はすべてのペアを順に調べるため、計算量は O(n²) となります。小規模な配列では十分実用的ですが、大規模データではより効率的なアルゴリズムの検討が必要です。

コード例

#include <bits/stdc++.h>
using namespace std;
int countPairs(int arr[], int n){
   // ペアの個数
   int count = 0;
   for (int i = 0; i < n-1; i++){
      for (int j = i + 1; j < n; j++){
         if(arr[i]%arr[j]==0 || arr[j]%arr[i]==0)
            { count++; }
      }
   }
   return count;
}
int main(){
   int Arr[] = { 2,3,4,5,6 };
   int len = sizeof(Arr) / sizeof(Arr[0]);
   cout << "ペアの個数 : "<< countPairs(Arr, len);
   return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

ペアの個数 : 3