1101 - 求两个正整数m,n的最大公约数

求任意两个自然数m和n的最大公约数

输入

12 20

输出

4

样例

输入

12 20

输出

4

输入

24 56

输出

8

提示

方法一:求任意两个自然数m和n的最大公约数,可以想到其最大的可能就是两个数中的较小者min,最小可能是1。所以,可以设最大公约数gcd从min开始进行判断,若gcd>1并且没有同时整除m和n,那么就gcd-1,重复判断是否整除。 方法二:求两个整数的最大公约数可以采用辗转相除法即欧几里德算法。对于任意两个自然数m和n,用m,n,r分别表示被除数、除数、余数,那么m和n的最大公约数等于n和r的最大公约数。以下是辗转相除法的算法: 1)求m除以n的余数r; 2)当r!=0,执行第3)步;若r==0,则n为最大公约数,算法结束。 3)将n的值赋给m,将r的值赋给n;再求m除以n的余数r。 4)转到第2)步

时间限制 10000 秒
内存限制 128 MB
讨论 统计
上一题 下一题