各要素がN以下となる一意なペアを見つけるC++プログラム

この記事では、要素がN以下であり、かつ以下の条件を満たす一意な数のペアを見つけるプログラムについて詳しく解説します。

• 2つの数の差の2乗が、それらの最小公倍数(LCM)と等しいこと。
• 2つの数の最大公約数(HCF)が、連続する2つの数の積として表せること。

問題を解くためのアプローチ

この問題を効率的に解くには、1から始まる連続する2つの数を取り、その積の倍数を順に調べる方法が有効です。その中からペアを特定するために、候補となる2つの数が最初の条件(差の2乗 = LCM)を満たしているかどうかを確認します。

具体例：2と3の場合

まず、2と3という連続する数を考えてみましょう。その積は6です。6の倍数を順に挙げると、6、12、18、24…となります。隣り合う2つの数を取り上げ、その差の2乗(この場合36)がそれらのLCMと等しいかを確認していきます。その結果、このケースでのペアは12と18であることがわかります。

一般化された式

この規則を一般化すると、2つの数はそれぞれ Z × (Z × (Z+1)) と (Z+1) × (Z × (Z+1)) で表されます。ここで、ZはHCF(連続するペアの積)における最初の数です。

さらに、値がN以下でなければならないという条件を適用すると、次の不等式が得られます。

(Z+1) × (Z × (Z+1)) ≤ N、すなわち Z³ + 2Z² + Z ≤ N

サンプルコード

#include <iostream>
using namespace std;
int main() {
    int N = 489, pairs, i = 1;
    //N以下の要素を持つペアの個数を数える
    while((i*i*i) + (2*i*i) + i <= N) {
        i++;
    }
    pairs = i;
    cout << "Pairs :" << endl;
    //ペアを構成する2つの要素を出力する
    for(int j = 1; j < pairs; j++) {
        cout << j*(j*(j+1)) << " " << (j+1)*(j*(j+1)) << endl;
    }
    return 0;
}

出力結果

Pairs :
2 4
12 18
36 48
80 100
150 180
252 294
392 448

このように、数学的な性質を活用することで、全ての組み合わせを総当たりで調べることなく、効率的に条件を満たすペアを求めることができます。