欧几里得算法的推广形式

xenium9

欧几里得算法用于计算两个非负整数的最大公约数：

1. long gcd(long a, long b)
2. {
3. if (b == 0) return a;
4. return gcd(b, a % b);
5. }

复制代码

可以推广该算法，使它能计算出满足下列条件的整系数x和y：d = gcd(a, b) = ax + by

1. // return d = gcd(a, b) = ax + by
2. long gcd(long a, long b, long &x, long &y)
3. {
4. if (b == 0) { x = 1; y = 0; return a; }
5. long d = gcd(b, a % b, y, x);
6. y -= a / b * x;
7. return d;
8. }

复制代码

注意，x与y可能为0或负数。这些系数对计算模乘法的逆是非常有用的。