本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-05-10 13:04:12

更好的阅读体验

温馨提示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}$也是一组解

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

$\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}$（$t$的正负可以代替加和减的分类讨论）

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$）

$x_{min}=(x_{tmp}\mod d+d)\mod d$（因为$x_{tmp}$有可能是负数）

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

$y_{min}=(y_{tmp}\mod d+d)\mod d$

5. 完结撒花

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

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