Tam giác không vuông

Xem PDF
Tác giả:
PhanDinhKhoi
Dạng bài
Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Để tham gia câu lạc bộ Origami của trường, Huy phải:

"Viết chương trình kiểm tra xem 3 số nguyên dương nhập vào có thể là 3 cạnh của một tam giác KHÔNG vuông hay không."

Vì laptop của Huy đã bị hỏng, bạn hãy giúp Huy giải bài tập trên.

Input

  • Dòng đầu tiên chứa 1 số nguyên dương \(T (T ≤ 10)\) - số test
  • Gồm \(T\) dòng, mỗi dòng chứa số nguyên dương \(a , b , c (a , b , c ≤ 10^{18})\)
    Các số trên một dòng của input file được ghi cách nhau bởi dấu cách

Output

  • Ghi ra "YES" nếu 3 số nguyên dương là 3 cạnh của của một tam giác KHÔNG vuông, ngược lại in ra "NO"

Example

Test 1

Input 
2
3 4 5
6 6 6
Output 
NO
YES

Bình luận


  • -2
    nguyentanhyhuu    3:25 p.m. 4 Tháng 11, 2022

    Kiểm tra: 

    a*a = b*b+c*c hoặc b*b = a*a+c*c hoặc c*c = a*a+b*b

    Nếu đúng thì in ra
    NO

    Nếu sai thì in ra
    YES


    • -1
      vietcuong_thathung    7:54 p.m. 7 Tháng 10, 2021

      UwU có nghĩa gì vậy

      1 phản hồi

      • -1
        ekhoavvdd    1:53 p.m. 24 Tháng 12, 2020

        test yếu hay sao mà ktra bình thường ko dùng bignum mà vẫn đúng :))


        • -21
          huybenten10    5:07 p.m. 18 Tháng 12, 2020

          Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


          • -5
            todonghai2k7    7:38 p.m. 19 Tháng 6, 2020

            Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

            2 phản hồi

            • -17
              todonghai2k7    7:32 p.m. 19 Tháng 6, 2020 ← chỉnh sửa 3

              Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


              • 1
                iloveroblox    5:52 p.m. 19 Tháng 6, 2020

                @SPyofgame có phải là wibu ko vậy mà sao toàn dùng emoji : OwO, UwU, ^w^

                1 phản hồi

                • 1
                  cuom1999    5:33 a.m. 19 Tháng 6, 2020

                  Một cách nữa là mod 2 vế cho một số nguyên tố nào đó. Cách này thì O(1) nhưng hên xui hơn

                  2 phản hồi

                  • 4
                    SPyofgame    2:27 a.m. 19 Tháng 6, 2020 ← chỉnh sửa 3

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

                    • -1
                      todonghai2k7    9:11 p.m. 18 Tháng 6, 2020 ← đã chỉnh sửa

                      strong text

                        • 1 bình luận nữa