AcWing 872题的最大公约数如何求法？
- 内容介绍
- 文章标签
- 相关推荐
本文共计370个文字，预计阅读时间需要2分钟。
题目：给定整数对求最大公约数给定：整数数量 $n$，整数对 $(a_i, b_i)$要求：求出每对整数的最大公约数。
输入格式：第一行包含一个整数 $n$。接下来 $n$ 行，每行包含一对整数 $a_i, b_i$。
输出格式：输出 $n$ 行，每行输出一个整数，表示每对整数的最大公约数。
题目
给定 $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;
}
本文共计370个文字，预计阅读时间需要2分钟。
题目：给定整数对求最大公约数给定：整数数量 $n$，整数对 $(a_i, b_i)$要求：求出每对整数的最大公约数。
输入格式：第一行包含一个整数 $n$。接下来 $n$ 行，每行包含一对整数 $a_i, b_i$。
输出格式：输出 $n$ 行，每行输出一个整数，表示每对整数的最大公约数。
题目
给定 $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;
}