C++で(i+j)がAとBの両方で割り切れる順序対(i, j)の個数を数える方法

問題概要

整数 N、M、A、B が与えられます。求めるのは、その和が A と B の両方で割り切れる正の整数の順序対 (i, j) の個数です。ここで、1 ≤ i ≤ N および 1 ≤ j ≤ M を満たすものとします。

解法としては、i と j について二重ループで全探索を行い、(i+j) % A == 0 かつ (i+j) % B == 0 が成立するたびにカウントを1ずつ増やしていきます。

具体例で確認してみましょう。

入力

N = 5, M = 10, A = 2, B = 3;

出力

(i+j) が A と B の両方で割り切れる順序対 (i,j) の個数: 9

説明

該当するペアは (1,5)、(2,4)、(2,10)、(3,3)、(3,9)、(4,2)、(4,8)、(5,1)、(5,7) の9個です。

入力

N = 10, M = 10, A = 10, B = 11;

出力

(i+j) が A と B の両方で割り切れる順序対 (i,j) の個数: 0

説明

条件を満たすペアは存在しません。

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

• 整数 N、M、A、B を受け取ります。

• 関数 sumDivisible(int n, int m, int a, int b) がすべての変数を受け取り、A と B の両方で割り切れる和を持つ順序対の個数を返します。

• ペアを数えるための変数 count を 0 で初期化します。

• i と j を求めるために二重の for ループで走査します。

• i は 1 から n まで、j は 1 から m まで繰り返します。

• (i+j) % a == 0 かつ (i+j) % b == 0 であるかを判定します。

• 条件が真であれば count をインクリメントします。

• すべてのループが終了した時点で、count には該当するペアの総数が格納されています。

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

計算量について

この手法では、i と j のすべての組み合わせを調べるため、時間計算量は O(N × M) となります。N と M が大きくなると処理時間が増加する点に注意が必要です。

コード例

#include <bits/stdc++.h>
using namespace std;
int sumDivisible(int n,int m,int a,int b){
    int count = 0;
    for (int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if((i+j)%a==0 && (i+j)%b==0)
                { count++; }
        }
    }
    return count;
}
int main(){
    int N = 50, M = 100, A = 5, B = 10;
    cout <<"Ordered pairs (i,j) where (i+j) is divisible by both A & B: "<<sumDivisible(N,M,A,B);
    return 0;
}

出力

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

Ordered pairs (i,j) where (i+j) is divisible by both A & B: 500