数论问题
扩展欧几里得算法初步
算法原理
题目
求二元一次方程 \(ax + by = \gcd(a,b)\) 的一组可行解。
解法
由辗转相除法可知
\[\gcd(a,b) = \gcd(b, a \bmod b)
\]
因此要解原方程，只需解
\[bx + (a \bmod b)y = \gcd(b, a \bmod b)
\]
不断递归下去，终究有 \(b=0\)，此时 \(a = \gcd(a,b)\)，代入 \(\begin{cases}x=1 \\ y =0\end{cases}\) 即可。
注意到
\[a \bmod b = a - b \cdot \Big \lfloor \frac{a}{b} \Big \rfloor
\]
因此，原方程变为
\[bx + (a - b \cdot \Big \lfloor \frac{a}{b} \Big \rfloor) y = \gcd(a,b)
\]
即
\[ay + b(x - y \cdot \Big \lfloor \frac{a}{b} \Big \rfloor) = \gcd(a,b)
\]
注意到上式与原式骨架相同，则每次递归时，解的代换规则为
\[\begin{cases}
x = y' \\
y = x' - y' \cdot \Big \lfloor \dfrac ab \Big \rfloor
\end{cases}
\]
二元一次不定方程计数问题
题目
给定不定方程 \(ax + by = c\)，求解的个数。
解法
根据裴蜀定理，方程有整数解当且仅当 \(\gcd(a,b) | ax + by\)。
利用扩展欧几里得算法可以求出方程 \(ax + by = \gcd(a,b)\) 的一组特解，记这组解为 \(\{x_0,y_0\}\)，并记 \(g = \gcd(a,b)\)。将该方程变形得
\[a \cdot \frac{x_0c}{g} + b \cdot \frac{y_0c}{g} = c
\]
因此原方程的一组整数特解 \(\{x_1, y_1\}\) 满足
\[\begin{cases}
x_1 = \dfrac{x_0c}{g} \\
x_2 = \dfrac{y_0c}{g}
\end{cases}
\]
因此
\[\forall d \in \mathbb{Q},\ a(x_1 + db) + b(y_1-da) = c
\]
因为需要保证 \(x_1+db,y_1-da \in \mathbb{Z}\)，所以只需使得 \(db,da \in \mathbb{Z}\)，进而 \(d\) 必须是 \(\dfrac{1}{g}\) 的整数倍，即所有可行的 \(d\) 中正的最小值为 \(\dfrac{1}{g}\)。
将其代入，得到最小的整数步长为 \(d_x = \dfrac{b}{g},\ d_y = \dfrac{a}{g}\)。
\(\forall s \in \mathbb{Z}\)，该方程组的通解为
\[\begin{cases}
x = x_1 + sd_x \\
y = y_1 - sd_y
\end{cases}
\]
界定
\[\begin{cases}
x > 0 \\
y > 0
\end{cases}
\]
可得
\[\begin{cases}
x_1 + sd_x > 0 \\
y_1 - sd_y > 0
\end{cases}
\]
即
\[-\frac{x_1}{d_x} \lt s \lt \frac{y_1}{d_y}
\]
由于 \(s \in \mathbb{Z}\)，那么
\[\Big \lceil \frac{-x_1 + 1}{d_x} \Big \rceil \le s \le \Big \lfloor \frac{y_1-1}{d_y} \Big \rfloor
\]
取值范围的两个端点即为 \(s\) 的最小取值和最大取值。正整数解的个数即为 \(s\) 的取值个数，右界减左界即可。