【C++】不等式 x*x + y*y < n を満たす異なる非負整数ペア（x, y）を数える方法

正の整数 N が与えられたとき、不等式 x² + y² < N を満たす「異なる非負整数のペア (x, y)」の個数を数えることを考えます。

x = 0 から x² < N の範囲、y = 0 から y² < N の範囲でそれぞれの値を順に試していき、x² + y² < N が成り立つ組み合わせが見つかるたびにペアのカウントを1つ増やします。

例で確認しよう

入力: n = 4
出力: 異なるペア数 = 4
説明: 条件を満たすペアは (0,0)、(1,1)、(0,1)、(1,0) の4つです。いずれも不等式 x² + y² < 4 を満たしています。

入力: n = 2
出力: 異なるペア数 = 3
説明: 条件を満たすペアは (0,0)、(0,1)、(1,0) の3つです。いずれも不等式 x² + y² < 2 を満たしています。

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

• 整数変数 N に、対象となる正の整数を格納します。
• 関数 countPairs(int n) は n を引数として受け取り、不等式 x² + y² < n を満たす異なる非負整数ペアの個数を返します。
• 変数 count に該当するペアの個数を保存します。初期値は 0 です。
• 外側のループで i = 0 から i² < n まで、内側のループで j = 0 から j² < n まで繰り返します。
• 各組み合わせについて i² + j² < n が成立していれば count をインクリメントします。
• 処理が完了したら count を結果として返します。

コード例

#include <iostream>
using namespace std;
int countPairs(int n){
    int count = 0;
    for (int i = 0; i*i < n; i++)
        for (int j = 0; j*j < n; j++) // x*x + y*y < n
            if(i*i + j*j < n)
                count++;
    return count;
}
int main(){
    int N = 4;
    cout << "Distinct Non-Negative integer pairs count: " << countPairs(N);
    return 0;
}

出力結果

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

Distinct Non-Negative integer pairs count: 4

計算量について

外側と内側のループはそれぞれ i² < n、j² < n の間だけ繰り返されるため、各ループは高々 √n 回しか実行されません。したがって全体の時間計算量は O(n) となり、必要な追加メモリは O(1) で済みます。条件を満たさない組み合わせを早めに除外することで、さらに効率化できる余地もあります。