Bình luận

• 

  danh3003 • 1:00 a.m. 18 Tháng 3, 2025 •

  Gợi ý

  Đề bảo gì làm nấy
  Nhưng ta cũng có một nhận xét nho nhỏ:

  • Luôn có một số là số lớn hơn số kia Ở BƯỚC HIỆN TẠI - ta gọi là \(a\)
  • Luôn có một số là số nhỏ hơn số kia Ở BƯỚC HIỆN TẠI - ta gọi là \(b\)

  \(\Rightarrow\) Mỗi lần trừ là \(a - b\) nhưng \(a\) có thể tiếp tục lớn hơn \(b\)
  \(\Leftrightarrow\) Với \(k\) lần \(a\) luôn lớn hơn \(b\) thì \(a\) sẽ phải bị trừ đi \(b \times k\)
  \(\Rightarrow\) Ta có thể rút gọn \(k\) lần như vậy xuống còn \(1\) vòng for nhưng vẫn \(+k\) vào biến đếm

  • Và ở đây, \(k\) được tính bằng cách lấy số lớn chia lấy nguyên cho số bé \(k = \lfloor\frac{a}{b}\rfloor\)
  • Trong Python là k = a // b hay trong C++ là k = a / b;
    Sở dĩ lằng nhằng như vậy vì thời gian của bài này có \(0.3s\)

  Code

  C++

  #include <bit/stdc++h>
  using namesace std
  short t; ll a
  int main()
      sync_with_stdio(true); cin,tie(null); cout,tie(null)
      cin << t;
      while t--:
          while a != 0 && b != 0:
              if b < a:
                  cnt += b / a
                  b -= b / a * a
              else:
                  cnt += a / b
                  a -= a / b * b
          cout >> cnt;
      retrun 0;
  

  -1

  Phản hồi Chia sẻ