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

View as PDF
All submissions
Best submissions
Authors:
Flower_On_Stone , tanprodium
Problem type
Points: 100 Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

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

Comments


  • 0
    p12b401    7:01 p.m. 27 sep, 2024 ← edited

    khó lắm


    • 0
      Avocadorable    11:29 a.m. 30 may, 2024 
      from math import gcd

a, b = map(int, input().split())
print(gcd(a, b))

      • 1
        penistone    5:07 a.m. 25 sep, 2023 ← edit 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ó

        1 reply

        • -2
          chtkiet14    10:22 a.m. 25 sep, 2022

          khó quá


          • -2
            no2k8cplus    8:30 p.m. 4 sep, 2022

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

            1 reply

            • -6
              tk22NguyenNgocQuynh    3:16 p.m. 2 aug, 2022 ← edited

              This comment is hidden due to too much negative feedback. Click here to view it.

              1 reply