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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
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
    p12b401    7:01 p.m. 27 Tháng 9, 2024 ← đã chỉnh sửa

    khó lắm


    • 0
      Avocadorable    11:29 a.m. 30 Tháng 5, 2024 
      from math import gcd

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

      • 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

            • -7
              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