浅谈扩展欧几里得

· · 个人记录

更好的阅读体验

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

温馨提示2：本文小字比较多，如果分辨率不够可以放大网页。

0. 扩展欧几里得是什么

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

怎么求ax+by=c (c\mod \gcd(a,b)=0)的解呢？

1. ax+by=\gcd(a,b)

怎么求ax+by=\gcd(a,b)的解呢？

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

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

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

设另一个方程：bx_1+(a\mod b)y_1=\gcd(b,a\mod b)

设a_1=b,b_1=a\mod b

则该方程转化为a_1x_1+b_1y_1=\gcd(a_1,b_1)

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

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

我们首先研究如何从x_1和y_1推导出x_0和y_0，其他的就同理了

因为

\begin{cases}bx_1+(a\mod b)y_1=\gcd(b,a\mod b) \\ ax_0+by_0=\gcd(a,b)\end{cases}

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

所以

ax_0+by_0=bx_1+(a\mod b)y_1

且a\mod b=a-\lfloor\frac{a}{b}\rfloor b（好好体会一下）

所以

ax_0+by_0=bx_1+(a-\lfloor\frac{a}{b}\rfloor b)y_1 ax_0+by_0=bx_1+ay_1-\lfloor\frac{a}{b}\rfloor b y_1 ax_0+by_0=b(x1-\lfloor\frac{a}{b}\rfloor y_1)+ay_1 ax_0+by_0=ay_1+b(x_1-\lfloor\frac{a}{b}\rfloor y_1)

即\begin{cases}x_0=y_1 \\ y_0=x_1-\lfloor\frac{a}{b}\rfloor y_1\end{cases}

这样，我们就由x_1和y_1推导出了x_0和y_0，其他同理

于是乎：

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)的一组解

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

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

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

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

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

所以很简单：

\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=c的所有解\begin{cases}x=x_{ans}\\y=y_{ans}\end{cases}

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

即ax_{tmp}+by_{tmp}=c

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

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

在x_{tmp}上减，在y_{tmp}上加也同理

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

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

## 4. $x$和$y$各自的最小正整数解 以$x$的最小正整数解为例： 求出任意一组解$\begin{cases}x=x_{tmp} \\ y=y_{tmp}\end{cases}

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

同理对于$y$，设$d=\frac{a}{\gcd(a,b)}$（注意这里分子是$a$） $y_{min}=(y_{tmp}\mod d+d)\mod d

5. 完结撒花

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

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