【C++】1からaと1からbのペアのうち、合計がNで割り切れる組の数を数える方法

整数 a、b、n が与えられます。ここで x は 1 以上 a 以下の整数、y は 1 以上 b 以下の整数とし、これらを組み合わせて作られるすべてのペア (x, y) のうち、合計値 (x + y) が n で割り切れるペアの総数を求めるのが今回の課題です。

入出力の例

例1

入力： int a = 2, b = 3, n = 2

出力： 合計がNで割り切れるペアの数 ― 3

説明：

まず、1 から a（=2）までの整数は「1, 2」です。
次に、1 から b（=3）までの整数は「1, 2, 3」です。
作成できるペアは (1,1)、(1,2)、(1,3)、(2,1)、(2,2)、(2,3) の6通りで、
それぞれの合計は 2、3、4、3、4、5 となります。
このうち n（=2）で割り切れるのは 2、4、4 の3つなので、答えは 3 です。

例2

入力： int a = 4, b = 3, n = 3

出力： 合計がNで割り切れるペアの数 ― 4

説明：

1 から a（=4）までの整数は「1, 2, 3, 4」、1 から b（=3）までの整数は「1, 2, 3」です。
作成できるペアは全部で12通りあり、それぞれの合計は 2、3、4、3、4、5、4、5、6、5、6、7 です。
このうち n（=3）で割り切れるのは 3、3、6、6 の4つなので、答えは 4 です。

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

• 1〜a、1〜b の範囲と割る数として、整数変数 a、b、n を入力として受け取る
• 後続の処理のため、すべての値を関数に渡す
• ペアの個数を保持する一時変数 count を用意する
• i を 1 から a まで繰り返す外側の for ループを開始する
• その内側で、j を 1 から b まで繰り返す for ループを開始する
• ループ内で sum に i + j を代入する
• sum % n == 0 が成立するかどうかを判定し、成立していれば count を 1 増やす
• count を返す
• 結果を出力する

C++実装例

#include <iostream>
using namespace std;

int Pair_a_b(int a, int b, int n){
    int count = 0;
    for (int i = 1; i <= a; i++){
        for (int j = 1; j <= b; j++){
            int temp = i + j;
            if (temp % n == 0){
                count++;
            }
        }
    }
    return count;
}

int main(){
    int a = 2, b = 20, n = 4;
    cout<<"1からaと1からbまでのペアのうち、合計がNで割り切れる組の数: "<<Pair_a_b(a, b, n);
    return 0;
}

出力結果

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

1からaと1からbまでのペアのうち、合計がNで割り切れる組の数: 10

計算量に関する補足

この手法はすべてのペア (i, j) を二重ループで確認するため、時間計算量は O(a × b) となります。a と b が小さい範囲では十分に実用的ですが、値が大きくなる場合は、各数を n で割った余りの分布（剰余の出現回数）を事前に集計して組み合わせを数えることで、線形時間での効率化も可能です。