Ex-GCD
使用该算法可求出 \(ax+by=\gcd(a,b)\) 的一组解。
应用：
- 求解形如 \(ax+by=c\) 的不定方程。
下面讲解详细步骤：
step 1 判定解的情况：方程有解当且仅当 \(c \mid \gcd(a,b)\)。
step 2 在求 gcd 的过程中解方程：
我们有
\[ax'+by'\\
=\gcd(a,b)\\
=\gcd(b,a \bmod b)\\
=bx''+(a \bmod b)y''\\
=bx''+(a-\lfloor \frac{a}{b} \rfloor \times b)y''\\
=ay''+b(x''-\lfloor \frac{a}{b} \rfloor y'')
\]
比较系数得
\[\begin{cases}
x'=y''\\
y'=x''-\lfloor \frac{a}{b} \rfloor y''
\end{cases}
\]
即得到 \(x',y'\) 与 \(x'',y''\) 的关系。
这样，当递归到边界时，\(b=0\)，则有 \(ax'=a \Rightarrow x'=1\)。
因此，将 \(x' \leftarrow 1,y' \leftarrow 0\)（事实上，\(y'\) 可以为任意值，但设为 \(0\) 不容易溢出）即可倒推回出最开始的 \(x',y'\)。
得到原来的 \(x'\) 之后，它还不是原方程的解，需要令 \(x \leftarrow \frac{x' \times c}{\gcd}\)。若求最小非负整数解，则应令 \(b\) 除掉 \(\gcd\) 之后让 \(x\) 模它即可，原因可见下面例题的同余方程。
总之，不管需不需要，实现的时候都应该先把 \(a,b,c\) 全都除掉 \(\gcd\)，并且让 \(x\) 模 \(b\)，这样最保险。