印象中之前每次复习扩展欧几里得算法时,Google到的大佬们对扩欧的解释常常晦涩难懂。因此,在这文章中,我将根据自己的理解,试图以一种优雅的方式解释扩展欧几里得算法,希望能够使读者对扩展欧几里得算法形成直观而专业的理解。
先决条件
欧几里得算法
在了解扩展欧几里得算法前,当然要先知道欧几里得算法是什么。
如果你还不会求GCD,请先到 {% post_link oi-number-theory-quickpow-gcd-eulersieve 这里 %} 复习一下欧几里得算法。
int gcd(int a, int b)
{
if (a % b)
return gcd(b, a % b);
else
return b;
}
裴蜀定理
裴蜀定理的描述是这样的:
被称为裴蜀等式。
这里不多解释,知道有这个定理就行。
扩展欧几里得算法
正如裴蜀定理所介绍的那样,扩展欧几里得算法的产生源自于对裴蜀等式的求解问题:
这里所说的求解当然是指要求 的整数解。
推导
可以看出,这是一个不定方程,整数解有无穷多个。可以证明,如果我们找到一组解 ,则该方程的通解为:
在欧几里得算法中,我们用gcd(a, b)
这个函数来计算 的最大公约数,计算过程中需要递归地返回gcd(b, a % b)
的值。
类比地,我们试图用exgcd(a, b, x, y)
来求解裴蜀等式,此函数返回的仍然是 的最大公约数,并利用C++的引用特性在计算过程中将我们所需的裴蜀等式的解 带出。可以猜想,此过程中需要递归计算exgcd(b, a % b, x, y)
,也就是求解以下方程:
而 其实就是 。
这里的 应该不是裴蜀等式所需要求的 ,但是二者之间应该具有某种联系。可以尝试将这个方程的左式化简一下:
然后我们就惊讶地发现下面这两个方程具有相同的结构:
欲解第一个方程,须先解第二个方程。换句话说,如果我们想利用 exgcd(a, b, x, y)
这样的函数求解裴蜀等式,要先求exgcd(b, a%b, x, y)
,获得 值之后,令:
至此我们就完成了扩展欧几里得算法中,下层递归结果对上一层的转化。
在欧几里得算法中,递归的临界条件是输入的 ,此时 就是所求的最大公约数。同样的,在扩展欧几里得算法中,如果我们向下一直递归,最终输入的 中 将为 ,此时无论 如何取值,都有 ,因为:
然后在回溯的过程中,通过上述算法,层层计算 的值,最终可以得到最初的裴蜀等式的一组特解。
解决方案
int exgcd(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int k = x;
x = y;
y = k - a / b * y;
return d;
}
后续步骤
至此你恭喜你已经学会了扩展欧几里得算法(如果我的文章写的还行的话),现在你可以使用扩展欧几里得算法愉快地解决以下问题了。
线性同余方程
求形如 的线性同余方程。
这里
乘法逆元
如果一个线性同余方程 ,则 称为 的逆元,记作 。
请参见
{% post_link oi-number-theory-quickpow-gcd-eulersieve 【OI考古】数论基础 | 快速幂、最大公约数、线性筛素数 %}