Ước chung lớn nhất (Greatest Common Divisor)

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

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

Đề bài

Cho hai số nguyên không âm $a,b$, bảo đảm không đồng thời bằng 0. Tìm ước chung lớn nhất (UCLN) của hai số.

Input

Một dòng gồm hai số nguyên $a,b$.

Output

In một số nguyên là UCLN của $a,b$.

Subtask

• Subtask 1 (20%): $0\le a,b\le100$, $a+b>0$.
• Subtask 2 (30%): $0\le a,b\le10^9$, $a+b>0$.
• Subtask 3 (50%): $0\le a,b\le10^{18}$, $a+b>0$.

Ví dụ

Ví dụ 1

Input

0 18

Output

18

Giải thích

UCLN(0,18)=18; vòng while không chạy vì b=18? Ban đầu b=18, một phép dư 0%18=0 đưa (18,0), in18.

Ví dụ 2

Input

30 18

Output

6

Giải thích

30%18=12,18%12=6,12%6=0; in6.