gcd & exgcd
gcd
设 \(a=bk+c\)，显然有 \(c=a \bmod b\)。设 \(d \mid a,~d \mid b\)，则 \(c=a-bk, \frac{c}{d}=\frac{a}{d}-\frac{b}{d}k\)。由右边的式子可知\(\frac{c}{d}\) 为整数，即 \(d \mid c\) ，所以对于 \(a,b\) 的公约数，它也会是 \(b,a \bmod b\) 的公约数。反过来也需要证明：设 \(d \mid b,~d\mid (a \bmod b)\)，我们还是可以像之前一样得到以下式子 \(\frac{a\bmod b}{d}=\frac{a}{d}-\frac{b}{d}k,~\frac{a\bmod b}{d}+\frac{b}{d}k=\frac{a}{d}\) 。因为左边式子显然为整数，所以 \(\frac{a}{d}\) 也为整数，即 \(d \mid a\)，所以 \(b,a\bmod b\) 的公约数也是 \(a,b\) 的公约数。既然两式公约数都是相同的，那么最大公约数也会相同。所以得到式子
exgcd
设 \(ax_1+by_1=\gcd(a,b)\)，\(bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)\)
由欧几里得定理可知： \(\gcd(a,b)=\gcd(b,a\bmod b)\)
所以 \(ax_1+by_1=bx_2+(a\bmod b)y_2\)
又因为 \(a\bmod b=a-(\lfloor\frac{a}{b}\rfloor\times b)\)
所以
因为 \(a=a,b=b\) ，所以 \(x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2\)
将 \(x_2,y_2\) 不断代入递归求解直至 \(\gcd\) （最大公约数，下同）为 \(0\) 递归 \(x=1,y=0\) 回去求解。
设 \(x_0,y_0\) 为 \(ax+by=\gcd(a,b)\) 的一组特解。
设 \(x_1=\frac{x_0 c}{\gcd(a,b)}~y_1=\frac{y_0 c}{\gcd(a,b)}\)
则 \(x_1,y_1\) 为 \(ax+by=c\) 的一组特解
设任意 \(d\in Q\) ，那么
同时， \(x_1+db\) 与 \(y_1-da\) 需均为正数。
因为 \(x_1,y_1\in \text{Z}\)
所以我们需要 \(da\in \text{Z},db \in \text{Z}\) 。
当 \(d\) 取到最小可能的正值时 \(d_x=db,d_y=da\) 那么任意解中这两个变量与 \(x_1,y_1\) 的偏差一定分别是 \(d_x\) 和 \(d_y\) 的倍数。
显然最小时 \(d_x=\frac{b}{\gcd(a,b)}\)，\(d_y=\frac{a}{\gcd(a,b)}\) ，在 \(d=\frac{1}{\gcd(a,b)}\) 时取到
通解公式
\(s\) 是任意整数
两条性质：
- \(x\) 增大时 \(y\) 减小
- \(s\) 越大， \(x\) 越大， \(y\) 越小。
若我们限制 \(x>0\) 有 \(x_1+s d_x>0,s>-\frac{x_1}{d_x}\)
若我们限制 \(y>0\) 有 \(y_1-s d_y>0,s<\frac{y_1}{d_y}\)
所以 \(-\frac{x_1}{d_x}<s<\frac{y_1}{d_y}\)
因为 \(s\) 是整数，故