题目描述

欧几里得算法（辗转相除法）基于这样一个原理： 两个整数的最大公约数（GCD）等于其中较小的数与两数相除的余数的最大公约数。换句话说，我们可以通过将较大的数除以较小的数，求得余数，然后将原问题转化为求较小的数与余数的最大公约数。
这个过程可以不断重复，直到余数为零，此时较小的数即为最大公约数。

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

输入格式

两行整数，分别是整数 $a$ 和 $b$，满足 $1 \leq a, b \leq 10^6$。

输出格式

两个正整数的最大公约数。

120
36

12