Bình luận

• 
  

  0

  penistone    5:07 a.m. 25 Tháng 9, 2023 ← chỉnh sửa 3 →

  Gợi ý: sử dụng thuật toán Euclide mở rộng

  Gọi a,b là 2 số cần tìm GCD, ta có:
  Nếu a<b, đổi vị trí 2 giá trị (hay a=b, b=a) *có thể sử dụng lệnh swap(a,b) trong c++
  Ta có biến nào đó làm trung gian (như biến r)
  Trong khi a mod b khác 0, ta có:
  1: Gán r=a mod b
  2: Gán a=b
  3: Gán b=r
  Kết quả của bài toán sau khi kết thúc sẽ là b (nếu âm thì lấy giá trị tuyệt đối sử dụng hàm abs trong c++)
  VD trong c++:

  int GCD(int a, int b)
  {
      if (a<b) swap(a,b); //phải luôn có a>=b
      int r;
      while (a%b!=0)
      {
          r=a%b; a=b; b=r; //thao tác biến đổi
      }
      return abs(b); //trả về kết quả là giá trị tuyệt đối
  }
  

  
  Cứ yên tâm, công thức này có thể duyệt 10^5 cặp 10^6 và vẫn không bị TLE
  Có hàm __gcd(a,b) trong thư viện bits/stdc++.h để tìm GCD trong c++ nha ace, nhưng cần phải tính giá trị tuyệt đối của nó

5 bình luận nữa