1. 扩展欧几里得算法
1.1. 介绍
扩展欧几里得算法用于求 \(ax+by=\gcd(a,b)\) 的一组特解（整数解）。
推导如下：
设 \(\begin{cases}ax_1+by_1=\gcd(a,b)\\bx_2+(a\mod b)y_2=\gcd(b,a\mod b)\end{cases}\)
由欧几里得算法可知 \(\gcd(a,b)=\gcd(b,a\mod b)\)。
联立有：
\[ax_1+by_1=bx_2+(a\mod b)y_2
\]
\[ax_1+by_1=bx_2+(a-\left\lfloor\dfrac{a}{b}\right\rfloor\times b)y_2
\]
\[ax_1+by_1=ay_2+b(x_2-\left\lfloor\dfrac{a}{b}\right\rfloor\times y_2)
\]
可得：
\[\begin{cases}x_1=y_2\\y_1=x_2-\left\lfloor\dfrac{a}{b}\right\rfloor\times y_2\end{cases}
\]
最后在求 \(\gcd\) 的过程中求解 \(x,y\) 即可。
1.2. 常见技巧
二元一次不定方程通解
对于 \(ax+by=c\) 这种一元二次不定方程，由裴蜀定理可知，当 \(\gcd(a,b)\nmid c\) 时，此方程无整数解。
当有整数解时，我们将其转化为 \(ax+by=\gcd(a,b)\) 的形式，然后用扩展欧几里得算法求解。
我们设扩展欧几里得算法求出的解为 \(X,Y\)，\(ax+by=c\) 方程所求的一组特解为 \(x',y'\)，有：
\[\begin{cases}x'=\dfrac{Xc}{\gcd(a,b)}\\y'=\dfrac{Yc}{\gcd(a,b)}\end{cases}
\]
因为 \(ax'\) 与 \(by'\) 的和恒为 \(c\)，有：
\[a(x'+db)+b(y'-da)=c
\]
其中，我们要保证 \(x'+db,y'-da\) 均为整数，取得最小变化量：
\[\begin{cases}d_x=\dfrac{b}{\gcd(a,b)}\\d_y=\dfrac{a}{\gcd(a,b)}\end{cases}
\]
最后得出通解形式：
\[\begin{cases}x=x'+sd_x\\y=y'+sd_y\end{cases}
\]
接下来是关于正整数解的内容。
限制 \(x,y>0\)，解得：
\[\left\lfloor\dfrac{-x'+1}{d_x}\right\rfloor\le s\le\left\lceil\dfrac{y'-1}{d_y}\right\rceil
\]
至此，我们可以判断正整数解个数。当 \(s\) 取极值时，我们也可求出 \(x,y\) 的极值。