欧几里得算法的推广形式
欧几里得算法用于计算两个非负整数的最大公约数：long gcd(long a, long b){
if (b == 0) return a;
return gcd(b, a % b);
}可以推广该算法，使它能计算出满足下列条件的整系数x和y：d = gcd(a, b) = ax + by// return d = gcd(a, b) = ax + by
long gcd(long a, long b, long &x, long &y)
{
if (b == 0) { x = 1; y = 0; return a; }
long d = gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}注意，x与y可能为0或负数。这些系数对计算模乘法的逆是非常有用的。
页:
[1]