Ước số chung lớn nhất

Xem PDF

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Số nguyên dương \(p\) gọi là ước số chung lớn nhất của \(n\) 𝑣à \(m\) khi \(m\) 𝑣à \(n\) cùng chia hết cho \(p\)\(p\) là lớn nhất.

Viết chương trình nhập vào một số nguyên dương \(n,m\) (\(n,m \leq 10^{12}\)).

Hãy in ra ước số chung lớn nhất của \(n\) 𝑣à \(m\).

Input

  • Nhập \(2\) số nguyên dương \(n,m\).

Output

  • In ra ước số chung lớn nhất của chúng.

Example

Test 1

Input
54 72 
Output
18

Bình luận


  • 0
    BL7A23_KhuyếnĐX 8:48 p.m. 18 Tháng 1, 2024

    hình như cái test 5 hay test 6 của cái này sai hay sao í, output ra 111111111111 đúng mà

    1 phản hồi

    • -32
      minhkhoidepzai 3:44 p.m. 29 Tháng 11, 2020 đã 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

      • 17
        SPyofgame 9:13 p.m. 7 Tháng 6, 2020

        Spoiler Alert

        Hint 1:

        Gọi gcd(a, b) là ước chung lớn nhất của ab

        gcd(a, a) = gcd(0, a) = gcd(a, 0) = a

        gcd(a, b) = gcd(b, a) = gcd(|a - b|, b)

        Hint 2

        gcd(a, b) = gcd(b, a % b)

        Reference

        C++
        template<typename T> inline T gcd(T a,T b) { while (b != 0) swap(b, a %= b); return a; }
        
        1 phản hồi