关于扩展欧几里得

§算法介绍

扩展欧几里得算法，可以在辗转相除法的过程中求 $ax+by=\gcd(a,b)$ 的解

算法过程：

当到达递归边界的时候，$b=0,a=\gcd(a,b)$ 这时可以观察出来这个式子的一个解：

$$ a\times 1+b\times 0=\gcd(a,b)\\ x=1,y=0 $$

接下来在回溯的时候往回推 $x,y$。

$$ \begin{aligned} \gcd&=b\times x_1+(a \%b)\times y_1\\ &=b\times x_1 + \left [ a-(a/b)\times b\right ] \times y_1 \\ &= b\times x_1 + a\times y_1 – (a/b)\times b\times y_1 \\ &= a\times y_1 + b\times (x_1 – a/b\times y_1) = gcd \\ \end{aligned} $$ 得：$x = y_1 , y = x_1 – a/b*y_1$

代码：

1
2
3
4
5


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

它有如下应用：

求解不定方程
求解模的逆元
求解线性同余方程

§求解不定方程

我们希望求出 $ax+by=c$ 的解。

首先根据裴蜀定理，$\gcd(a,b)\nmid c$ 时无解。

我们先用扩欧找到 $ax+by=\gcd(a,b)$ 的解 $x_0,y_0$。

然后$x_1= x_0\times \frac{c}{\gcd(a,b)}$，$y_1= y_0\times \frac{c}{\gcd(a,b)}$就得到了 $ax+by=c$ 的解。

$x_1$ 和 $y_1$ 是方程的特解，通解的话$x=x_1+ \frac{b}{\gcd(a,b)}\times k$，$y=y_1+ \frac{a}{\gcd(a,b)}\times k$

§求解模的逆元

即求 $ax\equiv1 \pmod{p}$ 最小整数解 $x$

将问题转化为 $ax+kp=1$ 即可用求解不定方程的方程解决。

§求解线性同余方程

即求 $ax\equiv b \pmod{p}$ 的解。

和逆元一样，将问题转化为 $ax+kp=b$ 即可用求解不定方程的方程解决。