C++で不等式 x² + y² < n を満たす非負整数ペア (x, y) の個数を数える方法

問題概要

正の整数 N が与えられたとき、不等式 x*x + y*y < N を満たす非負整数ペア (x, y) の組み合わせが何通りあるかを求めます。ここで、x と y は 0 以上の整数です。

基本的な考え方はシンプルです。x を 0 から x*x < N を満たす範囲、y を 0 から y*y < N を満たす範囲で順番に調べていき、条件 x*x + y*y < N が成立するたびにペアのカウントを 1 増やします。

入力例

n=4

出力例

distinct pairs= 4

説明 ― 条件を満たすペアは (0,0)、(1,1)、(0,1)、(1,0) の 4 つです。これらはすべて不等式 x² + y² < 4 を満たしています。

入力例

n=2

出力例

distinct pairs= 3

説明 ― 条件を満たすペアは (0,0)、(0,1)、(1,0) の 3 つです。これらはすべて不等式 x² + y² < 2 を満たしています。(1,1) は 1 + 1 = 2 となり条件を満たさないため除外されます。

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

• 整数変数 N に正の整数を格納します。

• 関数 countPairs(int n) は n を引数として受け取り、不等式 x² + y² < n を満たす非負整数ペアの個数を返します。

• 変数 count に該当するペアの数を保持し、初期値は 0 とします。

• 外側のループで i を 0 から i² < n の範囲、内側のループで j を 0 から j² < n の範囲で回します。

• i² + j² < n が成り立つ場合、count をインクリメントします。

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

C++コード例

#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

計算量について

このアルゴリズムでは、外側のループは高々 √N 回、内側のループも高々 √N 回しか実行されないため、全体の時間計算量は O(√N × √N) ＝ O(N) となります。N が大きくなっても現実的な時間で処理できる効率的な手法です。なお、(0,1) と (1,0) のように順序が異なるペアは別々にカウントされる点に注意してください。順序を区別しない組み合わせを数えたい場合は、j のループ開始点を i に変更することで重複を排除できます。