Hướng dẫn cho Tam giác không vuông

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

Spoiler Alert

Hint 1

  • Tìm điều kiện tam giác và loại bỏ điều kiện để nó vuông, từ đó suy ra kết quả

Điều kiện độ dài các cạnh: \((a > 0) \ \&\ (b > 0) \ \&\ (c > 0)\)

Điều kiện để tạo tam giác: \((a + b > c) \ \&\ (b + c > a) \ \&\ (c + a > b)\)

Điều kiện để tam giác vuông: \((a^2 + b^2 = c^2) || (b^2 + c^2 = a^2) || (c^2 + a^2 == b^2)\)

Hint 2

  • Ta cũng có thể sắp xếp các cạnh thành \(a \leq b \leq c\) để có công thức toán học gọn hơn

Điều kiện độ dài các cạnh: \((a > 0)\) (cạnh bé nhất dương)

Điều kiện để tạo tam giác: \((a + b > c)\) (tổng hai cạnh bé lớn hơn cạnh lớn nhất)

Điều kiện để tam giác vuông: \((a^2 + b^2 = c^2)\) (tổng bình phương hai cạnh góc vuông bằng cạnh huyền)

Hint 3

  • Ngoài bignum để nhân hai số lớn, ta có thể chuyển đổi toán học

\(a ^ 2 + b ^ 2 = c ^ 2 \Leftrightarrow \frac{a}{c - b} = \frac{c + b}{a}\)

Đưa hai phân số về tối giản, ta kiểm tra tử với từ, mẫu với mẫu là xong

Reference AC code | \(O(\log max\_val)\) time | \(O(1)\) auxiliary space | Math

C++
/// check a * a + b * b = c * c <=> a / (c - b) = (c + b) / a
inline bool isPythagorean(ll a, ll b, ll c) {
    pair<ll, ll> n1 = mp(a, c - b);     /// phan so thu nhat
    pair<ll, ll> n2 = mp(b + c, a);     /// phan so thu hai
    ll d1 = gcd(n1.first, n1.second);   /// ucln p/s thu nhat
    ll d2 = gcd(n2.first, n2.second);   /// ucln p/s thu hai
    n1.first /= d1;    n1.second /= d1; /// toi gian p/s thu nhat
    n2.first /= d2;    n2.second /= d2; /// toi gian p/s thu hai
    return (n1.first == n2.first && n1.second == n2.second); /// kiem tra hai p/s bang nhau
}

/// Voi moi truy van
int query()
{
    ll a, b, c;
    cin >> a >> b >> c;

    /// sort a < b < c  
    if (a > b) swap(a, b);
    if (a > c) swap(a, c);
    if (b > c) swap(b, c);

    if (a <= 0 || a + b <= c)   return cout << "NO\n", 0; /// (a, b, c) khong phai cac canh tam giac
    if (isPythagorean(a, b, c)) return cout << "NO\n", 0; /// (a, b, c) la cac canh tam giac vuong

    return cout << "YES\n", 0; /// (a, b, c) thoa man
}

Another Approach

  • Sài Hash + nhân ấn độ, bạn có thể kiểm tra trong \(O(1)\)

Reference AC code | \(O(\log max\_val)\) time | \(O(1)\) auxiliary space | Math, Hash

C++
/// cac so modulo nguyen to 18 chu so 
vector<ll> modulo = {
    100055128505716009,100707069199565201,101210328665281103,103509442668384329,103901850164540539,
    107164751690556253,108903531991843321,110356113559705927,110437474552301887,111991323706419863
};

/// nhan an do: (a * b) % m
inline ll mulMOD(ll a, ll b, ll m = MOD) {
    ll res = 0;
    for (a %= m, b %= m; b > 0; a <<= 1, b >>= 1) {
        if (a >= m) a -= m;
        if (b & 1) { res += a; if (res >= m) res -= m; }
    }
    return res;
}

/// ham kiem tra: check a * a + b * b = c * c <=> a / (c - b) = (c + b) / a
inline bool isPythagorean(ll a, ll b, ll c) {
    for (ll &m : modulo)
        if ((mulMOD(a, a, m) + mulMOD(b, b, m)) % m != mulMOD(c, c, m))
            return false;

    return true;
}

Bình luận


  • 0
    dtu_baphatnguyen    6:24 p.m. 17 Tháng 2, 2023

    Mình làm sort 3 số tăng dần xong check a+b>c và aa + bb!=c*c vẫn AC nha. Ko cần bignum hay Hash gì cả. Nhưng các biến để kiểu unsigned long long là ok nha. Đọc sol các bạn thấy hơi bất ngờ ahihi.