用递归求最大公约数 - Problem

Problem1053--用递归求最大公约数

1053: 用递归求最大公约数

_{[Creator : ]}

Time Limit : 1.000 sec Memory Limit : 256 MiB

Submit Solved: 45 Submit Num: 45 Statistics ShowOff!

Description

用递归方法求两个数 $x$ 和 $y$ 的最大公约数。$(1 \leq x,\ y \leq 5*10^9)$。

Input

输入两个整数 $x$ 和 $y$。

Output

输出一个整数。

Sample 1 Input

319 377

Sample 1 Output

HINT

求最大公约数可以使用辗转相除法：
假设a > b > 0，那么a和b的最大公约数等于b和a%b的最大公约数，然后把b和a%b作为新一轮的输入。
由于这个过程会一直递减，直到a%b等于0的时候，b的值就是所要求的最大公约数。
比如：
9和6的最大公约数等于6和9%6=3的最大公约数。
由于6%3==0，所以最大公约数为3。

Source/Category

基础算法 4.10.递推 4.11.递归

Submit