Problem LT: 最大公约数

Problem LT: 最大公约数

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

SubmitProblemList
Solved: 276Submit Num: 387Statistics

Description

用辗转相除法求两个正整数m、n的最大公约数。
辗转相除法， 又名欧几里德算法，是求最大公约数的一种方法。以除数和余数反复做除法运算，最终当余数为 0时，取当前算式除数为最大公约数。
例如，求125和45的最大公约数：
125÷45=2……35
45÷35=1……10
35÷10=3……5
10÷5 =2……0
所以125和45的最大公约数为5

Input

两个正整数m，n（0<m,n<10^9)。

Output

输出只有一行，为m和n的最大公约数。

Sample Input Copy 

3
6

Sample Output Copy 

3
Submit