python/TangDou/AcWing/Divisor/872.md

##AcWing 872. 最大公约数

一、题目描述

给定 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

二、解题思路

性质1：

若\large d|a　 且　 d|b, 则：

\large d | (a+b) \\
d | (a * x + b * y)$$

#### 性质2：
说明： $(a,b)$ 代表$a$和$b$的最大公约数
```c++
(a,b) =(b, a % b)
```
原理让李永乐老师的证明一下给你看： [https://v.qq.com/x/cover/0ekhxvyhbdh4h7u/n09564m4hsw.html](https://v.qq.com/x/cover/0ekhxvyhbdh4h7u/n09564m4hsw.html) 

#### 三种写法
常规写法
```c++
int gcd(int a, int b) {
   if(b) return gcd(b,a % b);
   return a;
}
```
三元表示式写法
```c++
int gcd(int a, int b) {
    return b?gcd(b, a % b):a;
}
```
库函数写法
```c++
__gcd(a, b)
```
### 三、实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;

// 最大公约数，辗转相除法
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;
        printf("%d\n", gcd(a, b));
    }
    return 0;
}
```