一、exgcd的概念
exgcd，全称为extended Euclidean algorithm，即扩展欧几里得算法。顾名思义，它是一种扩展版的欧几里得算法，可用于求解两个整数之间最大公约数以及对应的贝祖等式系数。通常情况下，我们只需要求解最大公约数即可满足需求，而对于贝祖等式系数，其用处比较广泛，如在密码学中用于求解模反元素等问题。
二、求解最大公约数
求解两个整数的最大公约数问题是exgcd应用最广泛的领域之一。具体做法如下：
// exgcd求解最大公约数
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int gcd = exgcd(b, a % b, y, x);
y -= a / b * x;
return gcd;
}上述代码使用了递归的方式来求解最大公约数。需要注意的是，递归边界为$b=0$的情况，此时$x$和$y$各自为1和0，最大公约数为$a$。
三、求解贝祖等式
在exgcd求解最大公约数过程中，我们也同时求解了贝祖等式系数$x$和$y$。对于贝祖等式$a\times x+b\times y=gcd(a,b)$而言，我们可以将其视为一种线性方程，进而通过倍增、高斯消元、矩阵快速幂等方式进行求解。下面是使用倍增法的求解方式：
// a*x+b*y=gcd(a,b)的通解
pair<int, int> exgcd(int a, int b) {
int x = 1, y = 0, lastx = 0, lasty = 1;
while (b != 0) {
int quotient = a / b;
int temp = b;
b = a % b;
a = temp;
temp = x;
x = lastx - quotient * x;
lastx = temp;
temp = y;
y = lasty - quotient * y;
lasty = temp;
}
return make_pair(lastx, lasty);
}当然，在实际代码编写过程中，我们可能只需要一个解即可，因此也可以进行优化，将递增过程替换为单次求解。下面是对上述代码的小改进：
// a*x+b*y=gcd(a,b)的独特解
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int gcd = exgcd(b, a % b, y, x);
y -= a / b * x;
return gcd;
}
// 求解a*x+b*y=gcd(a,b)的解x
int exgcd(int a, int b, int gcd) {
int x, y;
exgcd(a, b, x, y);
return (x % (b / gcd) + b / gcd) % (b / gcd);
}四、应用举例
在具体应用中，exgcd的用处比较广泛，如以下几个场景：
情景1： 判断两个整数是否互质。
当两个整数互质时，其最大公约数为1。因此我们只需要判断exgcd返回的最大公约数是否为1即可。下面是相应的代码实现：
// 判断两个整数是否互质
bool is_coprime(int a, int b) {
return exgcd(a, b) == 1;
}情景2： 解决同余方程组。
同余方程组是以模同余关系为基础的方程组。通常我们可以通过中国剩余定理进行求解，而exgcd则是其最基础的组成部分。以例1为例：
例1: 求解同余方程组
$x\equiv 2(mod\;3)$
$x\equiv 3(mod\;5)$
通常情况下，我们可以使用中国剩余定理得到通解，但此处我们先使用exgcd求解该方程组：
pair<int, int> exgcd(int a, int b) {
int x = 1, y = 0, lastx = 0, lasty = 1;
while (b != 0) {
int quotient = a / b;
int temp = b;
b = a % b;
a = temp;
temp = x;
x = lastx - quotient * x;
lastx = temp;
temp = y;
y = lasty - quotient * y;
lasty = temp;
}
return make_pair(lastx, lasty);
}
// 求解同余方程组x=a1(mod m1),x=a2(mod m2)的通解，时间复杂度O(log(m1+m2))
int exCRT(int a1, int m1, int a2, int m2) {
int gcd = exgcd(m1, m2).first;
int x = ((a2 - a1) % m2 + m2) % m2 * exgcd(m1 / gcd, m2 / gcd).first % (m2 / gcd) * m1 % m2 + a1;
return gcd == 1 ? x : -1;
}上述代码实现了exgcd在求解同余方程组中的应用，时间复杂度为$O(log(m1+m2))$。
总结
exgcd是解决数学问题的一种基础工具，其应用范围比较广泛，通常用于求解最大公约数、贝祖等式、判断两个整数是否互质、解决同余方程组等问题。同样重要的是，掌握exgcd的理论知识，可以帮助我们更加深入理解相关算法、降低算法实现难度。本文从多个角度对exgcd做了详细的阐述，并提供了相应的代码实现，希望能够帮助读者更好地掌握这一重要的算法。
原创文章，作者：KWJI，如若转载，请注明出处：https://www.506064.com/n/149405.html
微信扫一扫 
支付宝扫一扫 