【例47.3】 最大公约数

解题思路

每组使用欧几里得算法，gcd(x,y)=gcd(y,x%y)，直到第二个数为0，输出第一个。

正确性说明

计算规则直接来自题目定义。按所述顺序处理时，已完成部分的结果被准确保存在累加量、计数或当前状态中；下一步只加入新增贡献。最终得到完整要求的结果。

易错点

C++11不使用std::gcd。

复杂度

n组，时间O(n log A)，空间O(1)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        int x, y;
        cin >> x >> y;
        while (y) {
            int r = x % y;
            x = y;
            y = r;
        }
        cout << x << "\n";
    }
    return 0;
}