python/TangDou/AcWing/Divisor/872.md

##[$AcWing$ $872$. 最大公约数](https://www.acwing.com/problem/content/description/874/)

### 一、题目描述
给定 $n$ 对正整数 $a_i,b_i$，请你求出每对数的最大公约数。

**输入格式**
第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个整数对 $a_i,b_i$。

**输出格式**
输出共 $n$ 行，每行输出一个整数对的最大公约数。

**数据范围**
$1≤n≤10^5,1≤a_i,b_i≤2×10^9$

**输入样例：**
```cpp {.line-numbers}
2
3 6
4 6
```

**输出样例：**
```cpp {.line-numbers}
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;
}
```