扩展欧几里得算法

前置知识

斐蜀定理（贝祖定理）

写在前面

鸣谢：扩展欧几里得算法——exgcd

Q：啥叫扩展欧几里得啊

A：扩展欧几里得算法是用来在已知 \(a, b\) 求解一组 \(x, y\) ，使他们满足斐蜀等式： \(ax + by = \gcd(a, b) = d\)

Update：2021/04/11：

实际上就是套了普通的辗转相除法，然后顺便求了两个量，使他们满足 \(ax + by = \gcd(a,b)\)，而已

下面主要讲推导过程

尝试搞一下它

先考虑一下比较简单的特殊情况，如果 \(b = 0\)，那么 \(\gcd(a, b) = a\)，并显然存在一组解 \(x = 1, y = 0\)

对于一般情况，设 \(ax + by = \gcd(a, b)\)，

根据欧几里得算法， \(\gcd(a, b) = \gcd(b, a \bmod b)\)

肯定存在式子 \(bx_2 + (a \bmod b)y_2 = \gcd(b, a \bmod b)\)

\[\therefore ax_1 + by_1 = bx_2 + (a \bmod b)y_2

\]

\[\begin{alignedat}{3}

\because ax_1 + by_1 & = bx_2 + (a - a \div b \times b)y_2 \\

& = bx_2 + ay_2 - a \div b \times b \times y_2 \\

& = ay_2 + b(x_2 - a \div b \times y_2)

\end{alignedat}\]

\[\therefore x_1 = y_2 , y_1 = x_2 - a \div b \times y_2

继续递归下去直到遇到我们一开始讨论的特殊情况再慢慢回溯就好啦~

实现代码：

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, x, y);
    int t = x;
    x = y, y = t - a / b * y;
    return Gcd;
}
           

不过毕竟有扩欧这种帅气的名字，可不能只干这点活

它还可以求逆元：

设 \(x\) 为 \(a\) 在模 \(p\) 意义下的逆元，那么满足式子：

\[ax \equiv 1

那么有：

\[ax + my = 1

然后用 \(exgcd\) 搞出 \(x\) 即可（这就是为啥 \(a\) 和 \(m\) 一定要互质才能使得 \(a\) 在模 \(m\) 意义下有逆元）

long long inv(long long a,long long m)
{
    long long x,y;
    long long d = exgcd(a, m, x, y);
    return d == 1 ? (x + m) % m : -1 ;//不互质就没有逆元
}
           

\(The\) \(end.\)