Problem E: 【递归】利用辗转相除法求最大公约数

Problem E: 【递归】利用辗转相除法求最大公约数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 344  Solved: 250
[Submit] [Status] [Web Board] [Creator:]

Description

本题要求实现一个递归函数:利用辗转相除法求最大公约数。

函数接口定义:

int gcd(int a, int b);

裁判测试程序样例:


辗转相除法,是目前已知最古老的算法, 可追溯至公元前300年。 
它首次出现于欧几里德(Euclidean)的《几何原本》(第VII卷,命题i和ii)中,在中国可以追溯至东汉时期的《九章算术》 
辗转相除法计算两个正整数a和b的最大公约数,步骤描述如下: 
(1) 如果b为0则最大公约数为a,算法结束 
(2) 令r为a÷b所得余数 
(3) 令a←b,b←r,并返回步骤(1) 

特别提醒,本题要求必须用递归算法实现。

Input

输入正整数a,b;

测试数据有多组,处理到输入结束。

Output

输出a和b的最大公约数,每个输出占1行。

Sample Input Copy

24 60
18 15
23 21

Sample Output Copy

12
3
1