C++で「積が和で割り切れる」1からNまでの数値ペアを数える方法

整数 N が与えられたとき、1 から N までの数値の中から、2 つの数の積がその和で割り切れるようなペア (i, j) の個数を求めるのがこの記事の目標です。

例で理解しよう

入力 − N = 11

出力 − 条件を満たすペアの数：1

説明 − 3 と 6 のペアに注目すると、積は 18、和は 9 であり、9 は 18 を余りなく割り切ることができます。N = 11 の範囲内ではこれが唯一のペアです。

入力 − N = 30

出力 − 条件を満たすペアの数：12

説明 − 該当するペアは次の 12 個です。

(3, 6)、(4, 12)、(5, 20)、(6, 12)、(6, 30)、(8, 24)、(9, 18)、(10, 15)、(12, 24)、(15, 30)、(20, 30)、(21, 28)

プログラムで使うアプローチ

基本的な考え方はシンプルで、FOR ループを二重に回して 1 から N までのすべての数値の組み合わせを調べます。各 i に対して、積 (i × j) が和 (i + j) で割り切れるような j を探し、条件を満たす i ≠ j のペアが見つかるたびにカウントを 1 ずつ増やしていきます。

• 数値 N を入力として受け取ります。
• 関数 Sum_N(N) は N を引数に取り、「積が和で割り切れるペアの個数」を戻り値として返します。
• 外側のループで i を 1 から N 未満まで走査します。
• 内側のループで j を i + 1 から N まで走査します（同じ数同士のペア i = j は除外）。
• カウント用変数 count の初期値を 0 とします。
• 各 (i, j) の組み合わせについて、temp = (i × j) % (i + j) を計算します。
• temp が 0 になれば、和が積を完全に割り切っていることを意味するので、count をインクリメントします。
• すべてのループが終了した時点で、count には条件を満たすペアの総数が格納されています。
• 最後に count を結果として返します。

なお、この手法の時間計算量は O(N²) です。N が大きくなると計算量が急増するため、小〜中規模の N に適した素直な実装と言えます。

コード例

#include <bits/stdc++.h>
using namespace std;
int Sum_N(int N){
    int count = 0;
    for (int i = 1; i < N; i++){
        for (int j = i + 1; j <= N; j++){
            int temp = (j * i) % (j + i);
            if (!temp){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int N = 20;
    cout<<"Count of pairs of numbers from 1 to N with Product divisible by their Sum are: "<<Sum_N(N);
    return 0;
}

出力

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

Count of pairs of numbers from 1 to N with Product divisible by their Sum are: 6

N = 20 の場合、条件を満たすペアは 6 個存在することが確認できます。(3, 6)、(4, 12)、(5, 20)、(6, 12)、(8, 24)、(9, 18)、(10, 15) のうち、N = 20 以下に収まる組み合わせが該当します。