$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

板子。
为什么不用 __gcd(a, b) 呢？
………………

有 $gcd(a,b) = gcd(a,b + a \times k)$。
那么逆向一下就变成了辗转相减。

由辗转相减法改成辗转相除法。

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int a, b; scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }
    return 0;
}