Cánh Diều - GCD - Tìm ước chung lớn nhất hai số (T90)

Xem PDF
Tác giả:
Flower_On_Stone , tanprodium
Dạng bài
Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho hai số nguyên \(a, b\). Hãy tìm ước số chung lớn nhất của hai số \(a, b\).

Input

  • Gồm một dòng ghi hai số nguyên \(a, b\) cách nhau bởi dấu cách \((|a|, |b|\leq 10^6)\).

Output

  • Một số nguyên là ước số chung lớn nhất của hai số đã cho.

Example

Test 1

Input 
8 12
Output 
4

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ó


    • -2
      chtkiet14    10:22 a.m. 25 Tháng 9, 2022

      khó quá


      • -2
        no2k8cplus    8:30 p.m. 4 Tháng 9, 2022

        hàm gcd ko tính đc số âm

        1 phản hồi

        • -5
          tk22NguyenNgocQuynh    3:16 p.m. 2 Tháng 8, 2022 ← đã chỉnh sửa

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

          1 phản hồi