参考文章：https://zhuanlan.zhihu.com/p/100567253

欧几里得（辗转反侧相除法）

//辗转相除法，求两个数的最大公因数
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a%b);
}

要记住的原理就是
求 gcd(75,48)

拓展欧几里得

什么是拓展欧几里得呢？这是一种算法，它可以在辗转相除途中求出不定方程 的一组解。

裴蜀定理

设 为正整数，则关于 的方程 有整数解当且仅当是 的倍数。

只要求 的解就好了，对于方程 ，只需要令 即可。

通过求 的解，可以得出 的解
前者等价于 ，也就是
对比系数发现，我们可以令：

和普通的辗转相除法相同，当 时递归结束，由上图右下角那个式子可知，此时应令 。

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y), x0 = x, y0 = y;
    x = y0;
    y = x0 - (a / b) * y0;
    //上面三行还能这样写
    //int d = exgcd(b, a % b, y, x);//在这里就交换了x、y
    //y -= (a / b) * x;
    return d;
}

使用该函数时，xy传入一个变量用于存储最后的结果即可.

int x,y;
exgcd(75, 48, x, y);
//此时x、y就是 75x+48y=gcd(75,48) 的特解了

通解简单记忆一下：（推导可以去看参考文章）

来点题目

洛谷| P1082 [NOIP2012 提高组] 同余方程

所谓 ，其实就相当于 ，移下项就是 。
于是我们可以用拓展欧几里得算法求解
有解的条件是 ，即 、 互质,即 、 互质，那么通解就是 。(上面的小记忆）
那么已知 要求最小正整数解，只需求 就好了，但因为C++对模的处理，如果 是负数，这里得到的是最大负整数解，所以需要再加上一个 。出于简化书写，可以统一加上b然后再模b

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i =n;i<m;++i)
int egcd(int a, int b, int&x, int&y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    int d = egcd(b, a%b, y, x);
    y -= (a / b) * x;
    return d;
}
int main()
{
    ios::sync_with_stdio(false);
    int a, b, x, y;
    cin>>a>>b;
    egcd(a, b, x, y);
    int res = ((x%b)+b)%b;
    cout<<res;
    return 0;
}