C++で配列内の a % b = k を満たすすべてのペア（a, b）を検索する方法

問題の概要

配列 A が与えられたとき、その中から a % b = k を満たすすべてのペア（a, b）を見つけることを考えます。たとえば、配列 A = [2, 3, 4, 5, 7]、k = 3 の場合、条件を満たすペアは (7, 4)、(3, 4)、(3, 5)、(3, 7) となります。

ここで注意したいのは、(a, b) が順序付きペアであるという点です。つまり (3, 4) と (4, 3) は別々の候補として扱われ、それぞれ剰余演算の結果が k と一致するかどうかが個別に判定されます。

解法のアプローチ

この問題は、ブルートフォース（総当たり）法によって解くことができます。手順は以下のとおりです。

• 配列内のすべての要素の組み合わせ（i, j）を二重ループで走査する
• 各組み合わせに対して arr[i] % arr[j] == k が成り立つかを判定する
• 条件を満たしたペアはその場で出力し、フラグを立てる
• ループ終了後にフラグが立っていなければ、「ペアが見つからなかった」ことを報告する

二重ループを使用するため、時間計算量は O(n²) となります。小規模〜中規模の配列であれば十分に実用的な手法です。

C++での実装例

#include <iostream>
using namespace std;

bool displayPairs(int arr[], int n, int k) {
    bool pairFound = false; // ペアが見つかったかどうかのフラグ
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i] % arr[j] == k) {
                cout << "(" << arr[i] << ", " << arr[j] << ")" << " ";
                pairFound = true;
            }
        }
    }
    return pairFound;
}

int main() {
    int arr[] = { 2, 3, 4, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    if (!displayPairs(arr, n, k))
        cout << "No pairs found";

    return 0;
}

実行結果

(3, 4) (3, 5) (3, 6) (3, 7) (7, 4)

コードのポイント

• 二重ループによる全探索： 外側のループで被除数（a）、内側のループで除数（b）を順に選び、すべての順序付きペアを網羅的にチェックします。
• フラグ変数の初期化： ペア発見フラグは false で初期化し、条件を満たすペアが見つかった時点で true に更新します。こうすることで、1件も見つからなかった場合に正しく「No pairs found」を表示できます。
• ゼロ除算への注意： 実運用では、配列に 0 が含まれる可能性があるため、arr[j] != 0 のガード条件を追加すると安全です。

まとめ

配列内で a % b = k を満たすペアの検索は、二重ループによる単純な全探索で実装できます。計算量は O(n²) ですが、ロジックが明快で理解しやすいのが特徴です。より大規模なデータを扱う場合は、事前にソートやフィルタリングを行って候補を絞り込むなど、工夫の余地があります。