最大公约数(欧几里得/辗转相除法)

本文主要是介绍最大公约数(欧几里得/辗转相除法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
题意：给定n对正整数ai,bi，请你求出每对数的最大公约数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个整数对ai,bi。
输出格式
输出共n行，每行输出一个整数对的最大公约数。
数据范围
1≤n≤1e5,
1≤ai,bi≤2∗1e9
输入样例：
2
3 6
4 6
输出样例：
3
2
思路：常识知识：如果a%d = 0 && b%d = 0, 那么(a + b)%d = 0,甚至(ax + by)%d = 0; 所以 gcd(a, b) = gcd(b, a % b).
代码实现：

#include<iostream>
using namespace std;
//辗转相除求gcd的模板函数
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}
int main()
{int n;cin >> n;while(n --){int a, b;cin >> a >> b;cout << gcd(a, b) << endl;}return 0;
}

这篇关于最大公约数(欧几里得/辗转相除法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---