扩展欧几里得详解——同余方程

对于同余方程的话就是一个经典扩展欧几里得求逆元的题目。

这个可以转换成,我们需要求的只是x和k从而得到一组解。

通常我们会得到a和b两个元素，假设a是7，b为40，通过扩展欧几里得进行运算。

这时也就是，我们第一步先开始从a，b两个数字里找到最大的那个

在这里的话是40，然后利用大的去除以小的也就是，5乘7得35，40-35余5。

• ① ，这个为我们的式子①号，我们先放一边。

然后这时，我们要用余数和7去进行比较谁大，这里是7大，所以用大的去除以小的也就是  

• ②，这个为我们的式子②号，因为我们的余数还未得到1，则继续此操作。

此时2与5去相比则为，余数为1了，那么写完最后一个式子就可以开始代换了。

• ③这个为我们最后的式子，因为已经得到1了，现在开始合并同类项

我们通过上面式子②替换掉式子中的2代入式子3中

• ④此时我们的新式子还一个5，那么代入式子①进入

这里的话我们用式子①将式子④中的5替换掉

• ⑤这时候进行合并同类项

⑤此时式子中还含有5这个元素我们继续使用式子①进行代换（将式子中所有元素代换为ax-by=1即可）

• ⑥然后进行合并同类项

⑥ 那么此时带入原式中则：

• 由于是负数，我们要将其化为正数，直接利用则结果为23

以上为扩展欧几里得数学演示。

下面为题目以及代码实现扩展欧几里得。

洛谷题目：P1082同余方程

输入：

输出：

#include <bits/stdc++.h>
#define simeple freopen("input", "r", stdin),freopen("output", "w", stdout);
#define fast ios::sync_with_stdio(false),cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

// 扩展欧几里得算法函数，计算 ax + by = gcd(a, b) 的解 (x, y) 和 gcd(a, b)
int exgcd(int a, int b, int &x, int &y) {
    if (!b) { // 如果 b 为 0，意味着 gcd(a, b) = a，此时 x = 1, y = 0
        x = 1;
        y = 0;
        return a;
    }
    // 递归调用，直到 b 为 0
    int d = exgcd(b, a % b, x, y);
    int t = x; // 保存当前 x 的值
    x = y; // 更新 x 的值为上一步 y 的值
    // 更新 y 的值为 t - (a / b) * y, 其中 t 是上一步的 x
    y = t - (a / b) * y;
    return d; // 返回 gcd(a, b)
}

// 用于求解模逆元，返回 a 在模 b 意义下的逆元，即 x 使得 ax ≡ 1 (mod b)
int Exgcd(int a, int b) {
    int x, y; // 用于存储扩展欧几里得算法的解
    int gcd = exgcd(a, b, x, y); // 计算 gcd(a, b) 及对应的 x, y
    // 返回 x 在模 b 意义下的正整数形式的逆元
    return (x % b + b) % b; 
}

int main()
{
    fast
    //simeple
    int a, b;
    cin >> a >> b;
    cout << Exgcd(a, b);
    return 0;
}