7114 - 辗转相除法

通过次数

70

提交次数

103

时间限制 : 1 秒
内存限制 : 128 MB

辗转相除法,又名欧几里得算法,是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法。

辗转相除法求两个数的最大公约数的步骤如下:
先用其中一个数除另外一个数,得第一个余数;
再用第一个余数除小的一个数,得第二个余数;
又用第二个余数除第一个余数,得第三个余数;

…………
这样逐次用后一个数去除前一个余数,直到余数是0为止。那么,最后一个除数就是所求的最大公约数。

请同学们设计一段程序,使用辗转相除法求任意两个数字的最大公约数

输入

输入一行两个正整数(均小于2^31),两个数字之间用空格隔开

输出

输出一行一个正整数

样例

输入

144 180

输出

36

输入

168 196

输出

28