扩展欧几里得算法（exgcd）

这是一道裸的扩展欧几里得算法的模板题，exgcd是一个在数论中运用广泛的算法，是中国剩余定理（crt）的前提知识。

欧几里得算法（辗转相除法）

欧几里得算法应该是最广为人知的数论算法了，哪怕你没有很深入接触数论，“辗转相除法”这个算法应该不会很陌生。辗转相除法的强大之处主要在于下面的一个式子：

$gcd(a,b)=gcd(b,a\%b),a\ge b$

这个式子给我们一个快速求两个数的gcd的方法，事实上辗转相除法的时间复杂度为$O(log n)$，下面是代码（假定a已经大于b）

//辗转相除法
int gcd(int a,int b)
{
    if(a%b == 0) return b;
    else return gcd(b,a%b);
}

扩展欧几里得算法

扩展欧几里得算法主要是用来求出方程$ax+by=gcd(a,b)$的解，运用欧几里得算法，我们对其进行一些变形和推导：

• ① 由于$gcd(a,b)=gcd(b,a\%b)$，我们可以把方程中的a换成b，把b换成a%b，则有方程$bx+(a\%b)y=gcd(b,a\%b)=gcd(a,b)$
• ② 由余数的定义，我们有$a\%b=a-b\left \lfloor a/b \right \rfloor$，带入①中的式子，得到$bx+(a-b\left \lfloor a/b \right \rfloor )y=gcd(a,b)$，再简单变形一下，得到$ay-b(x-\left \lfloor a/b \right \rfloor y)=gcd(a,b)$
• ③ 对于②式，再结合原方程，可以得出：若x1,y1是原方程的一组根，则另一组根x2,y2满足$x_{2}=y_{1},y_{2}=x_{1}-\left \lfloor a/b \right \rfloor y_{1}$

由这个递推式，我们只需在原来的辗转相除法的基础上顺便更新一下x,y即可，递归边界是b=0时，x=1,y=0

本题要求的是$ax\equiv 1 (mod\ \ b )$的最小正整数解，即变化成$ax+by=1$的最小正整数解，由裴蜀定理：方程$ax+by=c$有解的充要条件是$c \mid gcd(a,b)$，因此本题有解的条件是a,b互质，否则无解。既然如此，本题就变成了$ax+by=gcd(a,b)$，可以直接套用扩展欧几里得算法解决

代码如下：

#include <bits/stdc++.h>
using namespace std;

int a,b,x,y;

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

int main()
{
    scanf("%d%d",&a,&b);
    exgcd(a,b,x,y);
    printf("%d",(x%b+b)%b);
    return 0;
}

顺便一提：求同余方程$ax\equiv c (mod\ \ b )$，也就是$ax+by=c$时，判断有解只需要验证$c \mid exgcd(a,b)$，因为我们的exgcd函数的返回值仍然是a,b的最大公约数，只是把一组x,y通过引用传值的形式给到了参数中

这里说exgcd传值得到的是一组x,y，并不是我们想要的最小正整数解，因此在得到x后我们还需要一部操作x=(x%b+b)%b，理由是若x是方程的一个解，则x+b,x+2b,x+3b都是方程的解，这是显然的