拓展欧几里得算法
作用:
\[{\forall}a, b\in Z, 求出x,y,使得ax + by = (a, b) \]实现:
我们可以改造欧几里得算法:
int gcd(int a, int b){
if (!b){
return a;
}
return gcd(b, a % b);
}
设递归函数void exgcd(int a, int b, int &x, int &y)
能够使找到满足上述条件的x,y。
边界 : 当b = 0时,显然x = 1, y = 0.
当b != 0时,我们计算了exgcd(b, a % b, y, x)
\[即得到满足方程\ by + (a \ mod \ b)x = d 的x和y, d为a,b的最大公约数 \\ 将上式变形即 \ ax + (y - \lfloor \frac{a}{b} \rfloor)b = d \]由上式可得
\[设ax + by = d的解为x', y' \\ 则x' = x, y' = y -\lfloor \frac{a}{b} \rfloor \]也就是说,有了exgcd(b, a % b, y, x),我们就可以计算出exgcd(a, b, x, y),在计算的过程中就会不断更新x和y,代码如下
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
拓展欧几里得应用
1. 解线性同余方程
\[即解\ ax \equiv b \pmod m \\ 即\exist y \in Z, {\text st.} ax = my + b \\ ax - my = b \\ 令y' = -y \\ 即解ax + my' = b, 其中a, m,b给出 \]由欧几里得算法可以得到
\[ax_1 + my_1 = d,d = (a, m) \\ 显然 x = \frac{b}{d} x_1, y = - y' = \frac{b}{d}y_1 \]此方程有解的条件是:\((a, m) |b\)
2. 求逆元
\[ax \equiv 1 \pmod m \]这是\(b\)为\(1\)的线性同余方程,\(m\)不一定是质数