拓展的欧几里得算法计算逆元

扩展欧几里得算法用于计算两个整数a和b的最大公约数(GCD)，同时也找到了它们之间的贝祖等式的形式，即存在整数x和y，满足ax + by = GCD(a, b)。当我们要找到a关于b的逆元，也就是一个数k，使得(a * k) % b = 1时，这个算法就派上了用场。

具体来说，如果a不能被b整除，我们可以递归地应用扩展欧几里得算法，直到b变为0。这时，a就是gcd(a, b)，而余数的逆元就是返回的x。逆元的计算公式是通过回溯得到的，即x = y，y = x - (a / b) * y。

下面是C++实现的示例[^1]:

int exGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int r = exGcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return r;
}

当你调用`exGcd(a, b, &x, &y)`时，`x`将会存储a关于b的逆元。例如，如果你要找到15关于7的逆元，可以这样操作：

int x, y;
int gcd = exGcd(15, 7, x, y);
int inverse_of_15_mod_7 = x; // 这里会得到逆元的值

请注意，逆元只在模意义下定义，也就是说它是在模p的情况下存在的，因为我们在寻找的是满足(a * k) % p = 1的k。