题目描述

辗转相除法，也称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

两个整数的最大公约数（Greatest Common Divisor）是能够同时整除它们的最大的正整数,缩写为gcd。辗转相除法基于如下原理：

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数.

用数学语言表示就是：$gcd(a,b)=gcd（b，a$%$b)$

在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

例如，计算$a = 1071$和$b = 462$的最大公约数的过程如下：

(1)让$1071$除以$462$得到余数：$147$,所以$gcd(1071,462)=gcd(462,147)$

(2)让$462$除以$147$得到余数：$21$,所以$gcd(462,147)=gcd(147,21)$

(3)让$47$除以$21$得到余数：$0$,所以$gcd(147,21)=gcd(21，0)$

(4)此时较小的数已经是$0$，所以$gcd(21，0)=21$.

所以$gcd(1071,462)=21$

输入格式

一行2个自然数 $n$和$m$,保证$1\le m，n \le 10^9$。

输出格式

只有一行一个整数，表示$n$和$m$的最大公因数

36 24

12

2520 2160

360