温馨提示：本文推式子比较多，建议跟着文章自己推一推。
扩展欧几里得是什么
扩展欧几里得（exgcd）是一个可以用来求 \(ax+by=c\)（\(c\%\gcd(a,b)=0\)，否则无解）的解的算法
求解 \(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\%b)y_1=\gcd(b,a\%b)\)
令 \(a_1=b,b_1=a\%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\%b)y_1=\gcd(b,a\%b) \\ ax_0+by_0=\gcd(a,b)\end{cases} \]且根据欧几里得定理，\(\gcd(a,b)=\gcd(b,a\%b)\)
所以
\[ax_0+by_0=bx_1+(a\%b)y_1 \]且 \(a\%b=a-\lfloor\frac{a}{b}\rfloor b\)（模运算的意义）
所以
\[\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} \]这样，我们就由 \(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)\) 的一组解
\(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)}\)，得到
\[\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} \]在 \(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} \]\(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}\%d+d)\%d\)（因为 \(x_{tmp}\) 有可能是负数）
同理对于 \(y\)，设 \(d=\frac{a}{\gcd(a,b)}\)（注意这里分子是 \(a\)）
\(y_{min}=(y_{tmp}\%d+d)\%d\)
完结撒花
至此，你已经学完了扩展欧几里得的基础用法，如有不懂的地方，建议对照着文章自己推一推，悟一悟。
做个题练习一下吧：洛谷 P5656 【模板】二元一次不定方程 (exgcd)
标签：tmp,begin,frac,gcd,欧几里得,扩展,笔记,end,cases From： https://www.cnblogs.com/cxm1024/p/17168365.html