Bình luận

• 
  

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

10 bình luận nữa