问题 2820 --公约数 gcd [1*+]

2820: 公约数 gcd [1*+]

时间限制: 1 Sec  内存限制: 128 MB
提交: 23  解决: 18
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][28kb]

题目描述

输入两个数,求他们的最大公约数

Input

 两个数,分别是要求最大公因数的两个数

Output

 一个数——input的最大公因数

Sample Input

 10 5

Sample Output

 5

Hint

可以使用试除法,即从最小的那个数开始逐次减少1去试除,如果能同时被这两个整除,该数就是gcd。

方法二、用辗转相除,取余数后换位继续相除,取余数……
gcd(a,b) = gcd(b, a mod b) 边界 a=b 以及 b=0, b=1

输入

输出

提示

来源

[提交][状态]