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;
}