欧几里得算法的推广形式

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或负数。这些系数对计算模乘法的逆是非常有用的。