算法学习笔记：扩展欧几里得算法
扩展欧几里得算法
问题引入
求 \(ax+by=\gcd(a,b)\) 的一组整数解。
前置知识
欧几里得算法
当 \(a, b\) 为非负整数时，以下等式一定成立。
裴蜀定理
对于任意非负整数 \(a, b\) ，一定存在满足的整数对 \((x, y)\) ，使得以下等式成立。
问题求解
当 \(b=0\) 时，则有 \(ax = a\) ，因而此时有一组解，为 \(x=1,y=0\) 。
当 \(b \neq 0\) 时，由欧几里得算法，可得以下等式。
由裴蜀定理，得以下两个等式。
因为两个等式等价，因此可知 \(x = y_0, y = x_0 - \lfloor \cfrac{a}{b} \rfloor b y_0\) 。
递归算法，最后可以先求得一组特解 \((x', y')\) ，由特解构造通解，得以下式子。
对两个未知数一个加一个数，另一个减去一个数，让这个数达到最小就行。
扩展欧几里得算法
扩展欧几里得算法的过程，在上述的问题求解当中，其作用为：求解方程 \(ax + by = \gcd(a, b)\) 的一组特解 \((x_0, y_0)\) 。
具体的实现方式如下。
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int g, x1, y1;
g = exgcd(b, a % b, x1, y1);
x = y1; y = x1 - a / b * y1;
return g;
}
std::array<int,3> exgcd(int a, int b) {
if (b == 0) {
return {a, 1, 0};
} else {
auto [g, x1, y1] = exgcd(b, a % b);
return {g, y1, x1 - a / b * y1};
}
}
def exgcd(a : int, b : int):
if b == 0:
return a, 1, 0
g, x1, y1 = exgcd(b, a % b)
return g, y1, x1 - a // b * y1
不定方程
问题引入
求解 \(ax + by = c\) 的一组整数解。
问题分析
由裴蜀定理可知，对不定方程 \(ax_0 + by_0 = \gcd(a, b)\)，一定有整数解。当 \(\gcd(a, b) \mid c\) 时，一定存在整数解，否则无整数解。因此，我们可以先构建出两个式子。
可以发现，两个式子之间只差了 \(\cfrac{c}{\gcd(a, b)}\) 倍。因此，我们可以先使用扩展欧几里得算法求解 \(ax + by = \gcd(a, b)\) ，再对求出来的解乘上倍数 \(\cfrac{c}{\gcd(a, b)}\) ，我们就得到了方程的一组特解 \((x_0, y_0)\) 。
对于该不定方程，通解的构造也是一样的思路。
同余方程
问题引入
给定整数 \(a, b, m\) ，求解同余方程 \(ax \equiv b \pmod m\) 。
如果方程存在整数解，输出任意一个。
问题求解
同余方程可以转化为不定方程的形式。
我们将同余式转化为等式时，可以引入一个新的未知量。
由 \(ax \equiv b \pmod m\) ，可得 \(ax = m(-y) + b\) ，即 \(ax + my = b\) 。
我们只需要使用求解不定方程的方式求解该等式即可。