题目描述

简言之就是求两个数的最大公约数

欧几里得算法

要明白 d|a 和 b|a 如果都成立，那么 d | x1*a + x2*b也成立，明白了这个，我们就可以证明：
d|a 和 d|b 成立等价于 d|b 和 d|a - c*b(a % b) , c == a向下取整除以b;

C++ 代码

#include <iostream>
using namespace std;
int n;
int gcd(int a, int b){
    return b? gcd(b, a % b) : a;
}

int main(){
    cin >> n;
    while(n--){
        int x, y;
        cin >> x >> y;
        cout << gcd(x,y) << endl;
    }

    return 0;
}