Thuật toán Euclid trừ liên tiếp (Euclid by Repeated Subtraction)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho hai số nguyên dương $a,b$. Chỉ sử dụng phép so sánh và phép trừ để lặp thay đổi cặp số, tìm ước chung lớn nhất (UCLN) của chúng.

Input

Một dòng có hai số nguyên dương $a,b$.

Output

In UCLN của $a,b$.

Subtask

• Subtask 1 (20%): $1\le a,b\le100$.
• Subtask 2 (30%): $1\le a,b\le1000$.
• Subtask 3 (50%): $1\le a,b\le10000$.

Ví dụ

Ví dụ 1

Input

18 30

Output

6

Giải thích

(18,30)→(18,12)→(6,12)→(6,6), vậy UCLN bằng 6.

Ví dụ 2

Input

7 7

Output

7

Giải thích

Hai số đã bằng nhau; không cần trừ lần nào.