### 裴蜀定理(贝祖定理)

#### 定理
对任何整数 $a、b$ 和 $m$，关于未知数 $x$和 $y$ 的线性丢番图方程（称为裴蜀等式）：
$$\LARGE ax+by=m$$

* 有整数解时当且仅当 $m$是$a$及$b$的最大公约数$d=gcd(a,b)$的倍数。
* 裴蜀等式有解时必然有无穷多个整数解，每组解$x,y$都称为**裴蜀数**
* 可用扩展欧几里得算法求解**裴蜀数**

#### 例子
例如，$12$和$42$的最大公约数是$6$，则方程$12x + 42y = 6$有解。
事实上有:
* $(−3)×12+1×42=6$ 
* $4×12+(−1)×42=6$
* $11×12+(-3)*42=6$
* ...
  
用计算机帮着算一下：
```c++
#include <bits/stdc++.h>

using namespace std;
int main() {
    for (int x = -100; x <= 100; x++)
        for (int y = -100; y <= 100; y++)
            if (2 * x + y * 7 == 1) cout << x << " " << y << endl;
    return 0;
}
```

#### 证明
看这个证明可能要好懂点
例:
$$\LARGE 2 * x + 4 * y = c$$
那么$c$无论如何都是偶数，换句话来说，$c$一定是$2$的倍数$2 = gcd(2,4)$

$$\LARGE 3 * x + 9 * y = c$$
那么同理$c$一定是$3$的倍数，因为上述等于 : $3 * x + 3 * 3 * y = c$
$3 * (x + 3 * y) = c$，外面乘了个$3$，那么$c$再怎么都是$3$的倍数，$3 = gcd(3,9)$

那么这个定理有什么用呢。当$x，y$为整数解的时候，$c$一定是$gcd(a,b)$的倍数，那么我们就可以求得当为整数解的时候，$c$的最小值肯定就是$gcd(a,b)$ //最大公约数的$1$倍。


[用几何方式证明裴蜀定理](https://www.bilibili.com/video/av200767266/)
[点到直线距离的公式证明](https://www.toutiao.com/video/6815606337615954439/)

[练习题 P4549 【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549)

#### 实现代码
```c++
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int d = 0, a;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a);
        d = __gcd(d, abs(a)); 
    }
    printf("%d", d);
    return 0;
}
```
---

####　引理
<font color='blue' size=4><b>给定$a,b$，均是正整数且互质，那么由$ax+by，x>=0,y>=0$不能凑出的最大数是$ab-a-b$;</b></font>

[证明](https://blog.csdn.net/qq_38973721/article/details/79752734)


[练习题　蓝桥杯.买不到的数目](http://t.zoukankan.com/qwertiLH-p-9674097.html)

**解法I：采用引理解题**
```c++
#include<bits/stdc++.h>
using namespace std;
int main(){
   int a, b; 
   scanf("%d %d",&a,&b);
   printf("%d\n",a*b-a-b);
   return 0; 
}

```

**解法II:采用爆搜解题**
```c++
#include <bits/stdc++.h>
using namespace std;

int p, q, res;
/*
测试数据：
4 7

根据公式，最大无法凑出的是:4*7-4-7=17
*/
bool dfs(int x) {
    if (x == 0) return true;
    if (x >= p && dfs(x - p)) return true;
    if (x >= q && dfs(x - q)) return true;
    return false;
}

int main() {
    scanf("%d %d", &p, &q);

    for (int i = 1; i <= 1000; i++)
        if (!dfs(i)) res = i;

    printf("%d\n", res);
    return 0;
}

```
---