Tóm tắt đề bài

Cho số nguyên dương \(A\). Hãy kiểm tra xem có tồn tại tam giác vuông với ba cạnh nguyên \((a,b,c)\) (trong đó \(a^2+b^2=c^2\)) sao cho diện tích của tam giác bằng \(A\) hay không.

Diện tích tam giác vuông:

In YES nếu tồn tại, ngược lại in NO, với \(T \le 1000\), \(A \le 10^6\).

Phân tích

Ta cần kiểm tra có tồn tại cặp cạnh góc vuông nguyên \((a,b)\) sao cho:

• \(a^2+b^2\) là số chính phương (để tồn tại \(c\) nguyên),
• \(\frac{ab}{2}=A \iff ab = 2A\).

Nhận xét quan trọng:

• Điều kiện diện tích chỉ phụ thuộc vào tích \(ab\).
• Với \(ab=2A\), ta chỉ cần duyệt các ước \(a\) của \(2A\), đặt \(b=\frac{2A}{a}\) rồi kiểm tra Pythagore.
• Vì \(2A \le 2 \cdot 10^6\), số ước không nhiều; duyệt đến \(\sqrt{2A}\) là đủ.

Pitfall thường gặp:

• Dùng sqrt kiểu thực dễ sai do sai số; nên kiểm tra số chính phương bằng làm tròn và bình phương lại.
• Cần dùng kiểu long long vì \(a^2+b^2\) có thể tới \((2A)^2\) (với \(A=10^6\) thì \(\approx 4\cdot 10^{12}\)).

Hướng giải quyết

Nhận xét

Ta có:

Với mỗi ước \(a\) của \(2A\):

• \(b = \frac{2A}{a}\) là số nguyên.
• Tam giác vuông tồn tại khi và chỉ khi \(a^2 + b^2\) là số chính phương.

Chỉ cần tìm được một cặp thỏa mãn là trả lời YES.

Thuật toán

Với mỗi test \(A\):

1. Đặt \(M = 2A\).
2. Duyệt \(a\) từ \(1\) đến \(\lfloor \sqrt{M} \rfloor\):
   • Nếu \(M \bmod a \neq 0\) thì bỏ qua.
   • Đặt \(b = M/a\).
   • Tính \(s = a^2 + b^2\).
   • Kiểm tra \(s\) có phải số chính phương:
     • \(r = \lfloor \sqrt{s} \rceil\) (lấy long long r = sqrtl(s); rồi chỉnh).
     • Nếu \(r^2 == s\) thì in YES.
3. Nếu hết vòng lặp chưa thấy, in NO.

Vì sao đúng?

• Mọi tam giác vuông cạnh nguyên có diện tích \(A\) đều có \(ab=2A\), nên \((a,b)\) là một cặp ước của \(M=2A\).
• Khi ta duyệt toàn bộ ước \(a\) của \(M\) (tới \(\sqrt{M}\) là đủ vì ước đi theo cặp), ta chắc chắn xét đến cặp \((a,b)\) đó.
• Điều kiện \(a^2+b^2\) là chính phương tương đương tồn tại \(c\) nguyên sao cho \(a^2+b^2=c^2\).

Độ phức tạp

• Với mỗi test: duyệt \(a\) đến \(\sqrt{2A}\) nên \(O(\sqrt{A})\).
• Với \(A \le 10^6\): tối đa khoảng \(1414\) bước/test.
• Tổng: \(O(T\sqrt{A})\) đủ nhanh.
• Bộ nhớ: \(O(1)\).

Code tham khảo

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

static inline bool isPerfectSquare(long long x) {
    if (x < 0) return false;
    long long r = (long long) sqrtl((long double)x);
    // Chỉnh do sai số sqrtl
    while (r * r < x) ++r;
    while (r * r > x) --r;
    return r * r == x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        long long A;
        cin >> A;
        long long M = 2LL * A;

        bool ok = false;
        for (long long a = 1; a * a <= M; ++a) {
            if (M % a != 0) continue;
            long long b = M / a;

            long long s = a * a + b * b;
            if (isPerfectSquare(s)) {
                ok = true;
                break;
            }
        }

        cout << (ok ? "YES" : "NO") << "\n";
    }
    return 0;
}