题解：AcWing 872 最大公约数

【题目来源】

AcWing：872. 最大公约数 - AcWing题库

【题目描述】

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

【输入】

第一行包含整数 \(n\)。

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

【输出】

输出共 \(n\) 行，每行输出一个整数对的最大公约数。

【输入样例】

2
3 6
4 6

【输出样例】

3
2

【代码详解】

《AcWing 872 最大公约数》 #数学知识# #约数# #最大公约数# #欧几里得算法#

#include <bits/stdc++.h>
using namespace std;int n;  // 输入的计算次数// 计算两个数的最大公约数（GCD）
int gcd(int a, int b)
{// 递归终止条件：当b为0时，a即为最大公约数// 否则递归计算gcd(b, a % b)return b ? gcd(b, a % b) : a;
}int main()
{// 输入需要计算GCD的次数cin >> n;// 处理每组输入while (n--){int a, b;cin >> a >> b;  // 输入两个整数// 计算并输出它们的最大公约数cout << gcd(a, b) << endl;}return 0;
}

【运行结果】

2
3 6
3
4 6
2