AcWing 872. 最大公约数

题目

给定 $n$ 对正整数 $a_i,b_i$，请你求出每对数的最大公约数。

输入格式 第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个整数对 $a_i,b_i$。

输出格式 输出共 $n$ 行，每行输出一个整数对的最大公约数。

数据范围 $1≤n≤10^5,1≤a_i,b_i≤2×10^9$ 输入样例：

2
3 6
4 6

输出样例：

3
2

思路

一种流传比较广的算法：辗转相除法

两个正整数 $a,b$，进行以下操作：a = b, b = a % b 直至 a % b == 0

代码

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    if (a % b == 0) return b;
    
    return gcd(b, a % b);
}

int main()
{
    int n;
    cin >> n;
    
    while (n -- )
    {
        int a, b;
        cin >> a >> b;
        
        cout << gcd(a, b) << endl;
    }
    
    return 0;
}