题目描述
辗转相除法，也称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》(第V卷命题i和ii)中，而在中国则可以追溯至东汉出现的《九章算术》。
两个整数的最大公约数(Greatest Common Divisor)是能够同时整除它们的最大的正整数,缩写为gcd。辗转相除法基于如下原理:
定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
用数学语言表示就是:gcd(a,b)= gcd(b，a%b)
在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。
例如，计算a = 1071和6= 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≤ m，n< 10^9.
输出
只有一行一个整数，表示n和m的最大公因数
样例输入
36 24样例输出
12