Đếm bộ ba Pythagoras (a,b,c) với a²+b²=c² và 1≤a≤b≤c≤n C++

Cho số nguyên n. Đếm số bộ ba (a,b,c) thỏa mãn: a² + b² = c² và 1 ≤ a ≤ b ≤ c ≤ n.

Ví dụ minh họa

Ví dụ 1:

• Input: N = 5
• Output: 1
• Giải thích: (3, 4, 5).

Ví dụ 2:

• Input: N = 3
• Output: 0

Mã nguồn C++ (Vét cạn O(n²))

#include <bits/stdc++.h>
using namespace std;

int countTriplets(int n) {
    int count = 0;
    for (int a = 1; a <= n; a++) {
        for (int b = a; b <= n; b++) {
            int sum = a * a + b * b;
            int c = sqrt(sum);
            if (c * c == sum && b <= c && c <= n) {
                count++;
                cout << endl << "a: " << a << " b: " << b << " c: " << c;
            }
        }
    }
    return count;
}

int main() {
    int N = 15;
    cout << "So bo ba Pythagoras: " << countTriplets(N);
    return 0;
}

Kết quả chạy chương trình

a: 3 b: 4 c: 5
a: 5 b: 12 c: 13
a: 6 b: 8 c: 10
a: 9 b: 12 c: 15
So bo ba Pythagoras: 4

Tối ưu hóa - Sinh bộ ba Pythagoras nguyên thủy (Euclid's Formula)

Mọi bộ ba Pythagoras nguyên thủy (gcd(a,b,c)=1) có dạng:

• a = m² - n²
• b = 2mn
• c = m² + n²

Với m > n > 0, gcd(m,n)=1, m-n lẻ.

Các bộ ba không nguyên thủy là bội số của bộ ba nguyên thủy: k×a, k×b, k×c.

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int countTripletsEuclid(int n) {
    int count = 0;
    for (int m = 2; m * m <= n; m++) {
        for (int n_ = 1; n_ < m; n_++) {
            if ((m - n_) % 2 == 0) continue; // m-n phải lẻ
            if (gcd(m, n_) != 1) continue;   // phải nguyên tố cùng nhau
            
            int a = m * m - n_ * n_;
            int b = 2 * m * n_;
            int c = m * m + n_ * n_;
            if (c > n) break;
            
            // Đảm bảo a ≤ b
            if (a > b) swap(a, b);
            
            // Đếm tất cả bội số k
            for (int k = 1; k * c <= n; k++) {
                count++;
                // cout << "k=" << k << ": " << k*a << " " << k*b << " " << k*c << endl;
            }
        }
    }
    return count;
}

Độ phức tạp

Lưu ý

• Code gốc dùng sqrt có thể bị sai do độ chính xác float với số lớn. Nên kiểm tra c*c == sum.
• Điều kiện b <= c luôn đúng vì c² = a² + b² > b² ⇒ c > b (với a>0).