扩展欧几里得学习笔记

发表于 更新于 分类于

温馨提示：本文推式子比较多，建议跟着文章自己推一推。

扩展欧几里得是什么

扩展欧几里得（exgcd）是一个可以用来求 ax+by=cax+by=c（c%gcd⁡(a,b)=0c\%\gcd(a,b)=0，否则无解）的解的算法

求解 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)

首先，如果 b=0b=0 的话，gcd⁡(a,b)=a\gcd(a,b)=a，则解为 {x=1y=0\begin{cases}x=1 \\ y=0\end{cases}

设此方程的解为 {x=x0y=y0\begin{cases}x=x_0 \\ y=y_0\end{cases}

那么我们需要做的就是将 ax0+by0=gcd⁡(a,b)ax_0+by_0=\gcd(a,b) 转化为 b=0b=0 的格式，这就要用到辗转相除法了。

设另一个方程：bx1+(a%b)y1=gcd⁡(b,a%b)bx_1+(a\%b)y_1=\gcd(b,a\%b)

令 a1=b,b1=a%ba_1=b,b_1=a\%b

则该方程转化为 a1x1+b1y1=gcd⁡(a1,b1)a_1x_1+b_1y_1=\gcd(a_1,b_1)

我们会发现它和原方程的格式是一样的，而且根据欧几里得原理，它可以一直递推到 anxn+bnyn=gcd⁡(an,bn)a_nx_n+b_ny_n=\gcd(a_n,b_n) 使得 bn=0b_n=0，就可以求得解 {xn=1yn=0\begin{cases}x_n=1 \\ y_n=0\end{cases}

那假设我们已经求得了该结果，那如何推导出 x0x_0 和 y0y_0 呢？

我们首先研究如何从 x1x_1 和 y1y_1 推导出一组合法的 x0x_0 和 y0y_0，其他的就同理了

因为

{bx1+(a%b)y1=gcd⁡(b,a%b)ax0+by0=gcd⁡(a,b)\begin{cases}bx_1+(a\%b)y_1=\gcd(b,a\%b) \\ ax_0+by_0=\gcd(a,b)\end{cases}

且根据欧几里得定理，gcd⁡(a,b)=gcd⁡(b,a%b)\gcd(a,b)=\gcd(b,a\%b)

所以

ax0+by0=bx1+(a%b)y1ax_0+by_0=bx_1+(a\%b)y_1

且 a%b=a−⌊ab⌋ba\%b=a-\lfloor\frac{a}{b}\rfloor b（模运算的意义）

所以

ax0+by0=bx1+(a−⌊ab⌋b)y1=bx1+ay1−⌊ab⌋by1=b(x1−⌊ab⌋y1)+ay1=ay1+b(x1−⌊ab⌋y1){x0=y1y0=x1−⌊ab⌋y1\begin{matrix} \begin{aligned} ax_0+by_0&=bx_1+(a-\lfloor\frac{a}{b}\rfloor b)y_1 \\ &=bx_1+ay_1-\lfloor\frac{a}{b}\rfloor b y_1 \\ &=b(x1-\lfloor\frac{a}{b}\rfloor y_1)+ay_1 \\ &=ay_1+b(x_1-\lfloor\frac{a}{b}\rfloor y_1) \end{aligned} \\ \begin{cases}x_0=y_1 \\ y_0=x_1-\lfloor\frac{a}{b}\rfloor y_1 \end{cases} \end{matrix}

这样，我们就由 x1x_1 和 y1y_1 推导出了 x0x_0 和 y0y_0，其他同理

于是乎：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct node
{
    int x,y;
};
node exgcd(int a,int b)
{
    if(b==0)
    {
        node tmp;
        tmp.x=1,tmp.y=0;
        return tmp;
    }
    node tmp=exgcd(b,a%b);//递归求出x_(k+1)和y_(k+1)
    node ans;
    ans.x=tmp.y,ans.y=(tmp.x)-a/b*(tmp.y);//推导出x_k和y_k
    return ans;
}

这样，我们就求出了 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b) 的一组解

ax+by=cax+by=c 的一组解 {x=xtmpy=ytmp\begin{cases} x=x_{tmp}\\y=y_{tmp} \end{cases}

我们已经求出了 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b) 的一组解 {x=x0y=y0\begin{cases} x=x_0 \\ y=y_0 \end{cases}

那么我们就可以知道 akx0+bky0=kgcd⁡(a,b)akx_0+bky_0=k\gcd(a,b)

又因为要求 cc 是 gcd⁡(a,b)\gcd(a,b) 的倍数（否则无解）

所以 k=cgcd⁡(a,b)k=\frac{c}{\gcd(a,b)}

所以很简单：

{xtmp=kx0=cgcd⁡(a,b)x0ytmp=ky0=cgcd⁡(a,b)y0\begin{cases} x_{tmp}=kx_0=\frac{c}{\gcd(a,b)}x_0 \\ y_{tmp}=ky_0=\frac{c}{\gcd(a,b)}y_0 \end{cases}

3.ax+by=cax+by=c 的所有解 {x=xansy=yans\begin{cases} x=x_{ans}\\y=y_{ans} \end{cases}

我们已经求出了 ax+by=cax+by=c 的一组解 {x=xtmpy=ytmp\begin{cases}x=x_{tmp} \\ y=y_{tmp}\end{cases}

即 axtmp+bytmp=cax_{tmp}+by_{tmp}=c

将它加上再减去 abgcd⁡(a,b)\frac{ab}{\gcd(a,b)}，得到

axtmp+abgcd⁡(a,b)+bytmp−abgcd⁡(a,b)=ca(xtmp+bgcd⁡(a,b))+b(ytmp−agcd⁡(a,b))=c\begin{matrix} ax_{tmp}+\frac{ab}{\gcd(a,b)}+by_{tmp}-\frac{ab}{\gcd(a,b)}=c \\ a(x_{tmp}+\frac{b}{\gcd(a,b)})+b(y_{tmp}-\frac{a}{\gcd(a,b)})=c \end{matrix}

在 xtmpx_{tmp} 上减，在 ytmpy_{tmp} 上加也同理

所以 {x=xtmp±bgcd⁡(a,b)y=ytmp∓agcd⁡(a,b)\begin{cases} x=x_{tmp}\pm\frac{b}{\gcd(a,b)} \\ y=y_{tmp}\mp\frac{a}{\gcd(a,b)} \end{cases} 也是一组解

这个变换进行多次，即可得到

{xans=xtmp+t×bgcd⁡(a,b)yans=ytmp−t×agcd⁡(a,b)\begin{cases} x_{ans}=x_{tmp}+t\times\frac{b}{\gcd(a,b)} \\ y_{ans}=y_{tmp}-t\times\frac{a}{\gcd(a,b)} \end{cases}

xx 和 yy 各自的最小正整数解

以 xx 的最小正整数解为例：

求出任意一组解 {x=xtmpy=ytmp\begin{cases}x=x_{tmp} \\ y=y_{tmp}\end{cases}

因为将 xtmpx_{tmp} 加或减 bgcd⁡(a,b)\frac{b}{\gcd(a,b)} 也成立，所以可设 d=bgcd⁡(a,b)d=\frac{b}{\gcd(a,b)}（注意这里分子是 bb ）

xmin=(xtmp%d+d)%dx_{min}=(x_{tmp}\%d+d)\%d（因为 xtmpx_{tmp} 有可能是负数）

同理对于 yy，设 d=agcd⁡(a,b)d=\frac{a}{\gcd(a,b)}（注意这里分子是 aa）

ymin=(ytmp%d+d)%dy_{min}=(y_{tmp}\%d+d)\%d

完结撒花

至此，你已经学完了扩展欧几里得的基础用法，如有不懂的地方，建议对照着文章自己推一推，悟一悟。

做个题练习一下吧：洛谷 P5656 【模板】二元一次不定方程 (exgcd)