总时间限制: 1000ms 内存限制: 65536kB

描述

给定两个正整数，求它们的最大公约数。

输入

有多组数据，每行为两个正整数，且不超过int可以表示的范围。

输出

行对应输出最大公约数。

样例输入

4 8
8 6
200 300

样例输出

4
2
100

思路

根据初等数论的欧几里得算法，我们可以知道：

已知2个正整数 a, b (其中 a > b )，他们的最大公约数 gcd(a, b) = gcd(b, a mod b)

边界条件为： gcd(a, 0) = a

代码

#include <iostream>
using namespace std;
int euclid(int a, int b) {
    int temp;
    if(a < b) {
        temp = a;
        a = b;
        b = temp;
    }
    if( b == 0 )  return a;
    else  return euclid(b, a % b);
}
int main() {
    int a, b;
    while( cin >> a >> b ) {
        cout << euclid(a, b) << endl;
    }
    return 0;
}