A-最大公约数（分治）

求 a,b 的 最大公约数 c

Input
有多组输入
每行两个整数a，b （0

Output
每行一个整数 为a，b的最大公约数

Sample Input
2 6
1 3
5 10
125 17
Sample Output
2
1
5
1

分析：
欧几里得算法（辗转相除法）：
如求12和15的最大公约数
15=1x12+3（x=15, y=12, x%y=3）
12=4x3+0 (x=12, y=3, x%y=0)
3=0+3 (x=3, y=0.return 3)

注意：写递归的时候一定要先写递归出口。

#include
using namespace std;
int gcd(int x,int y){
	if(y==0)//递归出口
		return x;
	else return gcd(y,x%y);
}
int main(){
	int a,b;
	while(scanf("%d%d",&a, &b)!=EOF)
	{
		printf("%dn",gcd(a,b));
	}
	return 0;
}