在 C++ 中扩展欧几里得算法的递归到底发生了什么？

Question

我知道什么是扩展欧几里得算法以及为什么在编程中使用它。这是一种非常有用的算法，用于查找数字的逆模。我知道如何在 C++ 中实现它，这就是我在下面在 C++ 中实现它的方式。

typedef pair<int, int> pii;

#define x first
#define y second

pii extendedEuclidean(int a, int b)
{
    if(b==0)
        return {a,0};
    else {
        pii d = extendedEuclidean(b, a%b);
        return {d.y, d.x - (d.y*(a/b))};
    }
}

现在，如果我想找到一个数字的反模，例如 13，其中 mod 是例如 1000007，那么我只需调用这个函数

pair<int, int> res = extendedEuclidean(13, 1000007);

那么结果是

res.first

我的问题是为什么以及在这个递归中究竟发生了什么？以及为什么它会产生正确的结果。

注意：这里 gcd(a, b) 必须是 1。

Answer 1

欧几里得算法计算一对数的最大公约数(a, b)（假设a>b）。它采用了观察到的任何最大公约数a和b也的约数a-b。原因如下：

让我们d成为除数。那么，a可以表示为a=d*kfor an integerk和b=d*lfor an integer l。然后，a-b=d*k-d*l=d*(k-l)。k-l又是一个整数。因此，d必须是 的除数a-b。

该算法所做的是尽可能多地从较大的数字中减去较小的数字。这是部分a%b。例如，如果a = 25和b = 7，a%b=4是b从 中减去3 次后得到的结果a。之后，新的a将小于b. 因此，您交换两个数字。这是您调用递归的部分：extendedEuclidean(b, a%b);

扩展的欧几里得算法做得更多。此外，它计算两个数字x和y，使得gcd(a, b) = x * a + y * b。这是它的完成方式：

在最后一次迭代中，您最终得到a'=gcd和b'=0。因此，您分别有gcd=a' * 1 + b' * 0、 where1和0arex'和y'。假设前一次迭代中的值是a''和b''。然后我们知道a'=b''和b'=a'' % b''。有了这个，我们发现b'=a''-(a''/b'')*b''（尽可能多地减去）。我们可以修改

gcd = a' * x' + b' * y'
gcd = b'' * x' + (a''-(a''/b'')*b'') * y'
    = a'' * y' + b'' * (x' - y' * (a''/b''))

因此，新的x''=y'和y''=x' - y' * (a''/b''). 这是您的退货声明return {d.y, d.x - (d.y*(a/b))};。

一个例子：

让a=25, b=7. 第一遍计算列a和b（从上到下）。这说明了递归调用。第二遍计算列x和y（从下到上）。这说明了返回语句：

 a  | b            |  x   | y                     | means
----+--------------+------------------------------+---------------------
 25 |  7           |  2   | -1 - 2 * (25/7) = -7  | 1 = 2 * 25 - 7 * 7 
  7 |  25 % 7 = 4  | -1   |  1 + 1 * (7/4)  =  2  | 1 = (-1) * 7 + 2 * 4
  4 |  7 % 4  = 3  |  1   |  0 - 1 * (4/3)  = -1  | 1 = 1 * 3 - 1 * 3
  3 |  4 % 3  = 1  |  0   |  1 - 0 * (3/1)  =  1  | 1 = 0 * 3 + 1 * 1
  1 |  3 % 1  = 0  |  1   |  0                    | 1 = 1 * 1 + 0 * 0

所以，你得到1 = 2 * 25 - 7 * 7地方2是结果的.first和-7是结果的.second。如果我们在mod 25，这将简化为：

1 == 2 * 0 - 7 * 7
1 == -7 * 7

因此，-7 == 18（即result.second）是 的乘法倒数7 (mod 25)。请注意，我交换了输入以避免不必要的第一次迭代。否则，它是result.first。