C++で二乗和がN（a² + b² = N）となるペア（a, b）を数える方法

整数 N が与えられたとき、「二乗の和が N になるような正の整数の順序付きペア（a, b）」をすべて見つけ出し、その個数を数えるのが本記事の目的です。

この問題は、方程式 a² + b² = N の解を探索することで解決できます。具体的には、a を 1 から √N までの範囲で順に調べ、それぞれの a に対して b を √(N − a²) として計算します。b がきれいな整数になれば、そのペアは条件を満たしていることになります。

それでは、具体例を使って理解していきましょう。

入力例 1

N = 100

出力例 1

a^2 + b^2 = N となるペア（a, b）の個数: 2

説明

該当するペアは (6, 8) と (8, 6) の2つ。
6^2 + 8^2 = 36 + 64 = 100

入力例 2

N = 11

出力例 2

a^2 + b^2 = N となるペア（a, b）の個数: 0

説明

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

アルゴリズムの流れ

本プログラムで採用しているアプローチは以下のとおりです。

• 整数 N を入力として受け取ります。

• 関数 squareSum(int n) は、二乗の和が n となる順序付きペアの個数を返します。

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

• for ループを用いて a を走査します。

• a は 1 から n の平方根（sqrt(n)）までの範囲で繰り返します。

• b の二乗（bsquare）を n − pow(a, 2) として計算します。

• b を sqrt(bsquare) として求めます。

• pow(b, 2) == bsquare が成り立てば b は整数であるため、count を 1 増やします。

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

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

この手法では計算量が O(√N) 程度に抑えられるため、すべての組み合わせを総当たりで調べるよりも効率的に解を求められます。

C++ 実装例

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int squareSum(int n){
    int count = 0;
    for (int a = 1; a <= sqrt(n); a++){
        int bsquare = n - (pow(a,2));
        int b = sqrt(bsquare);
        if(pow(b,2) == bsquare){
            count++;
        }
    }
    return count;
}
int main(){
    int N = 5;
    cout << "Count of pairs of (a,b) where a^2+b^2=N: " << squareSum(N);
    return 0;
}

出力

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

Count of pairs of (a,b) where a^2+b^2=N: 2

N = 5 の場合、1² + 2² = 5 および 2² + 1² = 5 がともに成立するため、(1, 2) と (2, 1) の2つのペアがカウントされます。