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

  • rock • 5:47 p.m. 25 Tháng 3, 2025 •

    uses crt;
    Function GCD(a,b:int64):int64;
    begin
    while b<>0 do
    begin
    a:=a mod b;
    a := a + b;
    b := a - b;
    a := a - b;
    end;
    GCD:=a;
    end;
    Function Abs(c:int64):int64;
    begin
    If c<0 then c:=0-c;
    Abs:=c;
    end;
    Var a,b:int64;
    begin
    readln(a,b);
    Writeln(Abs(GCD(a,b)));
    readln
    end.

    0
    Phản hồi
    • tranduyhieu123 • 9:04 p.m. 25 Tháng 2, 2025 • ← chỉnh sửa 11

      sos

      1
      Phản hồi
      • p12b401 • 7:01 p.m. 27 Tháng 9, 2024 • ← đã chỉnh sửa

        khó lắm

        0
        Phản hồi
        • 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
          Phản hồi
          • penistone • 5:07 a.m. 25 Tháng 9, 2023 • ← chỉnh sửa 12
            Gợi ý: sử dụng thuật toán Euclid 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ó

            3
            Phản hồi
            • chtkiet14 • 10:22 a.m. 25 Tháng 9, 2022 •

              khó quá

              -3
              Phản hồi
              • no2k8cplus • 8:30 p.m. 4 Tháng 9, 2022 •

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

                -2
                Phản hồi
                • tk22NguyenNgocQuynh • 3:16 p.m. 2 Tháng 8, 2022 • ← đã chỉnh sửa

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

                  -6
                  Phản hồi