Ước số chung lớn nhất (Khó)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
admin , daicadihoc
Dạng bài
Đ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 \(a\) và \(b\) khi \(a\) và \(b\) cùng chia hết cho \(p\) và \(p\) là lớn nhất.

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

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

Input

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

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


  • 19
    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 a và b

    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; }

    • -24
      a52027duonghn    4:22 p.m. 14 Tháng 5, 2022

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


      • 12
        obitidev    7:56 p.m. 28 Tháng 7, 2022

        @a52027duonghn bạn đấy gửi Hint cho những người chưa thể nghĩ ra lời giải muốn có cái tham khảo, hoặc những người muốn tìm kiếm cách làm tốt ưu hơn cách làm của mình,... Nếu bạn không muốn xem Hint của người khác thì đừng nhìn vào, đừng để ý Có nhiều bạn khác muốn xem mà.

        @SPyofgame nên ẩn Hint đi nha :))

    8 bình luận nữa