C++で最初のN個の自然数から合計がKで割り切れるペアの個数を求める

NとKという2つの整数が与えられたとき、最初のN個の自然数の中から選んだペアのうち、その合計がKで割り切れるものの個数を求めます。まずは具体例を見てみましょう。

入力例

N = 3
K = 2

出力例

1

この場合、合計がK（=2）で割り切れるペアは1つだけです。該当するペアは (1, 3) です。

アルゴリズム

この問題は、以下の手順で解くことができます。

• NとKを初期化します。
• 1からNまでの自然数を生成し、配列に格納します。
• カウント用の変数を0で初期化します。
• 二重ループを使って、配列内のすべてのペアを列挙します。
  • 各ペアの合計値を計算します。
  • 合計値がKで割り切れる場合は、カウントを1増やします。
• 最後にカウントを返します。

C++による実装

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。

#include <bits/stdc++.h>
using namespace std;

int countPairs(vector<int> arr, int N, int K) {
    int count = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            int sum = arr[i] + arr[j];
            if (sum % K == 0) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<int> arr;
    int N = 10, K = 5;
    for (int i = 1; i <= N; i++) {
        arr.push_back(i);
    }
    cout << countPairs(arr, N, K) << endl;
    return 0;
}

実行結果

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

9

この例では、N = 10、K = 5 のとき、合計が5で割り切れるペアは9組存在することが確認できます。

計算量について

このアプローチでは、すべてのペアを総当たりで調べるため、時間計算量は O(N²) となります。Nが大きいケースでは、各数値をKで割った余りの分布に着目することで、O(N + K) のより効率的な解法へと改善することも可能です。