4.最大公约数 - 蓝桥云课

最大公约数

题目描述

给定两个正整数 A,B，求它们的最大公约数。

输入描述

第1行为一个整数 T，表示测试数据数量。
接下来的 T 行每行包含两个正整数 A,B。
1≤T≤105，1≤A,B≤109。

输出描述

输出共 T 行，每行包含一个整数，表示答案。

输入输出样例

示例1

输入

5
2 4
3 7
5 10
6 8
7 9

输出

2
1
5
2
1

运行限制

• 最大运行时间：2s
• 最大运行内存：128M

思路：

模板

代码：

#include<iostream>
using namespace std;
typedef long long ll;
ll T;
ll A,B;
ll gcd(ll a,ll b)
{while(b){ll temp = a % b;a = b;b = temp; }return a;
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> T;while(T--){cin >> A >> B;cout << gcd(A,B) << '\n';}return 0;
}