拓展欧几里得除法

欧几里得除法

拓展欧几里得除法用于求解整数线性方程 $ax+by=\gcd (a,b)$ 的一组解，同时可以用来求模逆元（当 a 和 b 互质时，$\gcd (a,b)=1$）。

迭代公式的理解

在扩展欧几里得算法中，递归地利用普通欧几里得算法的步骤并通过回溯计算满足等式的整数解。以下是关键公式的推导与直观解释：

1. 余数表达：

   $a\mathrm{mod}b=a-\lfloor a/b\rfloor \cdot b$

   在欧几里得算法中，每一步将较大的数分解为较小数的倍数加余数。

2. 递归形式：

   $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$

   展开得：

   $a\cdot x_1+b\cdot y_1=b\cdot x_2+(a-\lfloor a/b\rfloor \cdot b)\cdot y_2$

   化简后得：

   $x_1=y_2,y_1=x_2-\lfloor a/b\rfloor \cdot y_2$

3. 递归基和回溯： 当 b=0b = 0 时：

   $x=1,y=0$

   递归的每一步根据上述公式计算 $x,y$，最终通过回溯构造出完整的解。

应用到逆元的场景

模逆元定义为满足 $ax\equiv 1(\mathrm{mod}p)$ 的整数 xx。可以将其转化为：

$$ax+py=1$$

即在扩展欧几里得算法的解中，模逆元为 $x\mathrm{mod}p$。

示例代码

以下是基于上述原理的代码实现：

void exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

求模逆元的调用可以类似这样：

long long modInverse(long long a, long long p) {
    long long x, y;
    exgcd(a, p, x, y);
    return (x % p + p) % p;
}