数论之拓展欧几里得

概要：

首先来看它进化前的样子，也就是人尽皆知的欧几里得算法，用辗转相除法求gcd。

ll gcd(ll a,ll b)
{
    
    return b?gcd(b,a%b):a;
}

而拓展欧几里得，则是在欧几里得算法的应用上进行了拓展。它在求解gcd的基础上，额外解决了一个问题——求解二元不定方程的通解，即$ax+by=m$，其中$a$,$b$,$m$为已知，$x$,$y$为未知量，要求解$x$和$y$的解。
 

正文：

首先，要满足方程有解的充要条件：$[(a,b)|m]$。
如果不满足，则方程无解。
ps: $(a,b)$表示$a$和$b$的最大公约数，而$|$是整除符号，也就是$m$是$gcd(a,b)$的倍数。这个我也不知道怎么证，可以算是易得吧，读者自行思考。
 
于是乎，原方程可以看成这样，$ax+by=t\times gcd(a,b)$。
可以发现，我们只要求出$ax+by=gcd(a,b)$的解，然后将其乘上$t$即可。
 

重点来了！！！

首先我们要求一组特解。
 
我们递归将$a$和$b$进行辗转相除法，到递归边界时，$a=gcd(a,b),b=0$。
此时方程$gcd(a,b)x+0\ast y=gcd(a,b)$的一组解我们可以轻松得到：$x=1,y=0$。
 
我们从上一级的$a$和$b$变到下一层的$a$和$b$后，方程的解也从上一层的$x$和$y$变成了下一层的$x$和$y$。所以我们在递归回溯的同时，通过下层的$x$和$y$来计算得到上一层的$x$和$y$。（具体步骤略）
于是，我们得到了方程的一组特解$x_0\times t$，$y_0\times t$。
于是，我们又得到了方程的通解$x=x_{0}t+\frac{kb}{gcd(a,b)},y=y_{0}t-\frac{ka}{gcd(a,b)}$。
 

模板：

ll ex_gcd(ll a,ll b,ll& x,ll& y)
{
    
    if(b==0)
    {
    
        x=1;y=0;
        return a;
    }
    ll g=ex_gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return g;
}

应用（exgcd求逆元）：传送门

关于逆元，也就是$a^{-1}$，这里不详细介绍了。
a在模p意义下逆元存在的充要条件：$[gcd(a,p)=1]$
 
当模数p为质数时，可以利用费马小定理：$a^{p-1}\equiv 1(modp)$
我们要求$ax\equiv 1(modp)$，此时$x$只要等于$a^{p-2}$就好了。
 
然后当模数p不为素数时，那就是拓展欧几里得啦。
要求解$ax\equiv 1(modp)$。其实就是求解$ax+py=1$的一组特解。恍然大悟，后面就不说了。
 

模板（拓欧求逆元）：

ll ex_gcd(ll a,ll b,ll& x,ll& y)
{
    
    if(b==0)
    {
    
        x=1;y=0;
        return a;
    }
    ll ans=ex_gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return ans;
}

ll inv(ll a,ll mod)//存在逆元条件：gcd(a,mod)=1
{
    
    ll x,y;
    ll g=ex_gcd(a,mod,x,y);
    if(g!=1)return -1;
    return (x%mod+mod)%mod;
}