Đếm cặp số nguyên không âm (x,y) thỏa x²+y²

Cho số nguyên dương N. Nhiệm vụ: đếm số cặp (x,y) với x,y ≥ 0 thỏa mãn x² + y² < N.

Ví dụ 1

Input – n = 4

Output – 4

Giải thích: Các cặp: (0,0), (0,1), (1,0), (1,1). Kiểm tra: 0<4, 1<4, 1<4, 2<4. Cặp (0,2): 4≮4 (loại).

Ví dụ 2

Input – n = 2

Output – 3

Giải thích: (0,0), (0,1), (1,0). Cặp (1,1): 2≮2.

Thuật toán đơn giản

Duyệt x từ 0 đến khi x² ≥ N.
Với mỗi x, duyệt y từ 0 đến khi y² ≥ N.
Nếu x² + y² < N, đếm++.

Ví dụ code

#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;
}

Kết quả

Distinct pairs: 4

Tối ưu hóa O(√N)

Với mỗi x, y_max = floor(√(N-1-x²)). Số y hợp lệ = y_max + 1.

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