exgcd 通解（新）

标签：frac gcd exgcd times ax 通解 div aligned

可能不全，老文章在这
什么是通解，我们知道二元一次方程，是如果只有一个式子，那么解会有无数个，而通解就是指让我们只找到一个解就可以推出其他所有解的式子。
注意以下变量都为整数。

知道了定义下面就是推式子了，首先设 \(x, y\) 是 \(ax + by = \gcd(a, b)\) 的一个解，那么有

\[y = \left[\gcd(a, b) - ax \right] \div b \tag 1 \]

再设一个解 \(x_0,y_0\)

\[x_0 = x + k \tag 2 \]

那么有

\[ax_0 + by_0 = \gcd(a, b) \]

所以

\[y_0 = [\gcd(a, b) - ax_0] \div b \tag{3} \]

由 \((3)\) 和 \((2)\) 得

\[y_0 = \left[\gcd(a, b) - ax - ak \right] \div b = [\gcd(a, b) - ax] \div b - \frac{a}{b} \times k \tag4 \]

由 \((4)\) 和 \((1)\) 得

\[y_0 = y - \frac{a}{b} \times k \tag 5 \]

我们要保证 \(y_0\) 是整数，且 \(y\) 又是整数, 那么 \(\frac{a}{b} \times k\) 就是整数，设 \(d = \gcd(a, b)\)
\(a = a' \times d, b = b' \times d\)，这里 \(a', b'\) 互质（如果他们不互质，\(d\) 就可以通过 \(a', b'\) 的公约数变大, 这就和我们d是最大公约数就矛盾了, 所以a'和b'互质）
此时有

\[\frac{a}{b} \times k = \frac{a'} {b'} \times k \]

因为 \(a'\) 和 \(b'\) 互质，那么 \(\frac{a'}{b'} \times k\) 要是想是整数的话，\(k\) 只能是 \(b'\) 的倍数（\(k =0\) 时整个就是
\(0\) 也是整数,，依旧满足要求）不然就消不掉 \(\frac{a'}{b'}\)的分母 \(b'\) ，就会产生小数, 就不是整数了，因此

\[k = n \times b', n \in \mathbb{Z} \]

又因为

\[b' * d = b \]

所以

\[b' = b \div d \]

所以

\[k = \frac{nb}{d} \]

所以

\[x_0 = x + n*b/d \tag6 \]

通过 \((5)\) 和 \((6)\) 可得

\[y_0 = y - \frac {na}{d} \tag7 \]

至此通解就出来了

\[\begin{aligned} x_0 &= x + \frac{b}{d} \times n \\ y_0 &= y - \frac{a}{d} \times n \end{aligned} \]

更常见的是这样的

\[\begin{aligned} x_0 &= x + k\times \frac{b}{d}，k\in \mathbb{Z} \\ y_0 &= y - k \times \frac{a}{d} \end{aligned} \]

附带最小正整数解就是

\[\begin{aligned} x & \bmod \frac{b}{d}\\ y & \bmod \frac{a}{d} \end{aligned} \]

对于代码中，因为 C++ 强大的取负模的特性，所以更准确代码形式的应该是

(x % (b/d) + b/d) % (b/d)

就相当于把所有的 \(\frac{kb}{d}\) 给删掉, 剩下的就是最小的正整数解。

标签：frac,gcd,exgcd,times,ax,通解,div,aligned
From： https://www.cnblogs.com/blind5883/p/18227200