นับคู่จำนวนเต็มบวก (x,y) ที่ x²+y²

กำหนดจำนวนเต็มบวก N หาจำนวนคู่ (x, y) ที่เป็นจำนวนเต็มบวกหรือศูนย์ (non-negative integers) และแตกต่างกัน (distinct pairs) ที่ทำให้ x² + y² < N

ตัวอย่าง

N = 4

Output: 4

คู่ที่เป็นไปได้: (0,0), (0,1), (1,0), (1,1)

ตรวจสอบ: 0<4, 1<4, 1<4, 2<4 ✓

N = 2

Output: 3

คู่ที่เป็นไปได้: (0,0), (0,1), (1,0)

ตรวจสอบ: 0<2, 1<2, 1<2 ✓ (1,1) ให้ 2 ไม่น้อยกว่า 2 ✗

แนวทางแก้ปัญหา

วน x จาก 0 ถึงที่ x² < N (คือ x < sqrt(N))
ในแต่ละ x, วน y จาก 0 ถึงที่ y² < N
ถ้า x² + y² < N นับ +1

ตัวอย่างโค้ด (ปรับปรุงจากต้นฉบับ)

#include <iostream>
using namespace std;

int countPairs(int n) {
    int count = 0;
    for (int x = 0; x * x < n; x++) {
        for (int y = 0; y * y < n; y++) {
            if (x * x + y * y < n) count++;
        }
    }
    return count;
}

int main() {
    int N = 4;
    cout << "Distinct pairs: " << countPairs(N) << endl;
    return 0;
}

ผลลัพธ์

Distinct pairs: 4

การปรับปรุงประสิทธิภาพ (Optimization)

ลูปใน y สามารถหยุดได้เร็วขึ้น:

for (int x = 0; x * x < n; x++) {
    int maxY = sqrt(n - 1 - x * x);  // y สูงสุดที่ y² < n - x²
    count += maxY + 1;  // y = 0 ถึง maxY
}

ลดความซับซ้อนจาก O(N) เป็น O(√N)

ตัวอย่าง N = 10

x=0: y²<10 → y=0,1,2,3 (4 ค่า)
x=1: y²<9  → y=0,1,2   (3 ค่า)
x=2: y²<6  → y=0,1,2   (3 ค่า)
x=3: y²<1  → y=0       (1 ค่า)
รวม = 11 คู่

โค้ดเวอร์ชันเร็ว

#include <iostream>
#include <cmath>
using namespace std;

int countPairsFast(int n) {
    int count = 0;
    for (int x = 0; x * x < n; x++) {
        int maxY = sqrt(n - 1 - x * x);
        count += maxY + 1;
    }
    return count;
}

int main() {
    for (int N = 1; N <= 20; N++) {
        cout << "N=" << N << ": " << countPairsFast(N) << endl;
    }
    return 0;
}

ความซับซ้อน

Brute force: O(N) – วน x,y จน √N แต่ละตัว → ~N รอบ
Optimized: O(√N) – วน x แค่ √N รอบ คำนวณ y ด้วย sqrt
พื้นที่: O(1)

ข้อสังเกต

"Distinct pairs" หมายถึงคู่ (x,y) ที่ต่างกันเป็นคู่ ไม่ใช่ x≠y (คู่ (0,0) นับได้)
โค้ดต้นฉบับมี lt; และ &minus เป็น HTML entities ควรเป็น < และ -

นับคู่จำนวนเต็มบวก (x,y) ที่ x²+y² < n ใน C++