python/TangDou/AcWing/Math/P4549.md

裴蜀定理(贝祖定理)

定理

对任何整数 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
• ...

用计算机帮着算一下：

#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倍。

用几何方式证明裴蜀定理 点到直线距离的公式证明

练习题 P4549 【模板】裴蜀定理

实现代码

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

---

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

证明

练习题　蓝桥杯.买不到的数目

解法I：采用引理解题

#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:采用爆搜解题

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

---