Đếm tam giác vuông có chu vi cho trước C++

Cho chu vi P. Đếm số tam giác vuông có độ dài cạnh nguyên a, b, c thỏa a + b + c = P và a² + b² = c² (c là cạnh huyền).

Ví dụ minh họa

Ví dụ 1:

• Input: P = 12
• Output: 1
• Giải thích: (3, 4, 5): 3+4+5=12, 3²+4²=5².

Ví dụ 2:

• Input: P = 10
• Output: 0

Mã nguồn C++ (Duyệt a, b)

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

int rightTriangles(int p) {
    int count = 0;
    for (int a = 1; a < p / 2; a++) {
        for (int b = 1; b < p / 3; b++) { // Code gốc có lỗi: b nên bắt đầu từ a+1
            int c = p - a - b;
            if (a + b > c && b + c > a && a + c > b) { // Bất đẳng thức tam giác
                if (a * a + b * b == c * c) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    int perimeter = 12;
    cout << "So tam giac vuong co chu vi " << perimeter << ": " << rightTriangles(perimeter);
    return 0;
}

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

So tam giac vuong co chu vi 12: 1

Sửa lỗi và tối ưu hóa

Code gốc có vấn đề: vòng lặp b bắt đầu từ 1 thay vì a+1, và giới hạn p/3 không chính xác.

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

int rightTrianglesFixed(int p) {
    int count = 0;
    // a < b < c, a + b + c = p
    // a < p/3 (vì a < b < c ⇒ 3a < p)
    for (int a = 1; a < p / 3; a++) {
        // b < c = p-a-b ⇒ 2b < p-a ⇒ b < (p-a)/2
        // b > a
        for (int b = a + 1; b < (p - a) / 2; b++) {
            int c = p - a - b;
            if (a * a + b * b == c * c) {
                count++;
            }
        }
    }
    return count;
}

// Tối ưu hơn: Duyệt c (cạnh huyền), sau đó a
int rightTrianglesOptimized(int p) {
    int count = 0;
    // c < p/2 (vì a+b > c ⇒ p-c > c ⇒ c < p/2)
    // c > p/3 (vì c là lớn nhất)
    for (int c = p / 3 + 1; c < p / 2; c++) {
        // a + b = p - c, a² + b² = c²
        // (a+b)² = a² + b² + 2ab ⇒ (p-c)² = c² + 2ab
        // 2ab = (p-c)² - c² = p² - 2pc
        // ab = (p² - 2pc) / 2
        // a, b là nghiệm của x² - (p-c)x + (p²-2pc)/2 = 0
        int sum = p - c;
        long long prod2 = 1LL * p * p - 2LL * p * c;
        if (prod2 % 2 != 0) continue;
        long long prod = prod2 / 2;
        
        // Kiểm tra a, b nguyên: discriminant = sum² - 4prod
        long long disc = 1LL * sum * sum - 4 * prod;
        if (disc < 0) continue;
        int sqrt_disc = sqrt(disc);
        if (1LL * sqrt_disc * sqrt_disc != disc) continue;
        
        // a = (sum - sqrt_disc) / 2, b = (sum + sqrt_disc) / 2
        if ((sum - sqrt_disc) % 2 == 0) {
            int a = (sum - sqrt_disc) / 2;
            int b = (sum + sqrt_disc) / 2;
            if (a > 0 && a < b && b < c) count++;
        }
    }
    return count;
}

Độ phức tạp

Lưu ý

• Điều kiện tam giác a+b>c tự động thỏa nếu a²+b²=c² và a,b,c>0.
• Cách duyệt c + phương trình bậc 2 nhanh nhất O(P).