文章目录

• 扩展欧几里得算法
• • 裴蜀定理
  • 欧几里得算法
  • 扩展欧几里得算法证明与实现
  • 线性同余方程

---

扩展欧几里得算法

裴蜀定理

ax + by能够凑出来的最小的值一定是a和b的最大公约数（d的一倍）。

应用：扩展欧几里得算法求系数x和y。

欧几里得算法

【代码模板】

LL gcd(LL a, LL b)
{
	if(b == 0) return a;
	return gcd(b, a % b);
}

扩展欧几里得算法证明与实现

设LL exgcd(a,b,x,y)是求解系数x,y的函数，返回值是gcd（a,b)，那么可以根据递归求出exacd（b,a%b,i,j)求出系数i，j

根据下面的推导得到x，y与i，j的关系：

【代码模板】

LL exgcd(LL a, LL b, LL &x, LL &y)// 通过引用传回
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);// 注意：这里换一下顺序y
    y -= a / b * x; // x = x1
    return d;
}

【题目链接】877. 扩展欧几里得算法 - AcWing题库

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);// 注意：这里换一下顺序y
    y -= a / b * x; // x = x1
    return d;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    while (n -- )
    {
        LL a, b, x, y;
        scanf("%lld%lld", &a, &b);
        
        exgcd(a, b, x, y);
        printf("%lld %lld\n", x, y);
    }
    
    return 0;
}

线性同余方程

【题目链接】878. 线性同余方程 - AcWing题库

a * x ≡ b (mod m)

----> ax = my + b（y为m的整数倍）

----> ax - my = b，令y1 = -y ----> ax + my1 = b

根据拓展欧几里得定理，只要 b 是 a与m最大公约数的倍数，即b为gcd(a, m)的倍数即有解！反之无解。

若b是最大公约数的倍数，由拓展欧几里得算法可以求出一个系数x:X1使得ax + my1 = d（d为a与m的最大公约数）

在有解情况下，由于d与b存在倍数关系，我们可以将ax + my1 = d两边同时扩大b/d倍，由于a与m都是定数，也就是说ax + my1 = b中的x也就是我们题目要求的x会在 上述拓展欧几里得算法求出一个系数x:X1的基础上乘上b/d倍。
// 即最后答案为：x= X1 * d / b % m

ax % m=b⟺ a⋅(x % m) % m=b

​ 所以对x % m仍是个答案
​ 因为输出要在int范围，所以%m

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a/b * x;
    return d;
}

// ax % m == b -- > ax = my + b ---> ax + my1 = b
int main()
{
    int n;
    scanf("%d", &n);
    
    while (n -- )
    {
        LL a, b, m, x, y;
        scanf("%lld%lld%lld", &a, &b, &m);
        
        LL d = exgcd(a, m, x, y);
        if(b % d) puts("impossible");//b 不是 d的倍数 则无解
        else printf("%lld\n",  LL(b/d) * x % m);
    }
    
    return 0;
}

学习内容参考：
acwing算法基础课