定义
设a和b不全为0,则存在整数x和y,使得a*x + b*y = gcd( a, b) = d,其中d为最大公约数。
实现原理
对于gcd( a, b) = d,用辗转相除法可以得到gcd( d, 0),此时把a = d,b = 0代入a*x + b*y = d中可以得到x = 1,y为任意值。现在将该过程进行逆推,以满足任何情况下的a*x + b*y = d:
方程a*x + b*y = d经过对a,b的一次辗转相除之后原方程变为b*x + (a%b)*y = d,将此式展开有b*x + (a -[ a/b]*b)*y = d (其中[a/b]代表a/b向下取整),合并同类项之后可得 a*y + b*(x – [a/b]*y) = d,那么若b*x + (a%b)*y = d的解为 x = X,y = Y,那么对于a*x + b*y = d的解则为x = Y,y = X – [a/b]*Y。
现给出一个表对以上结论予以验证:
实现代码如下:
1 long long ExtendedEuclid(long long a,long long b,long long& d,long long& x,long long& y) 2 { 3 long long tmp; 4 if(b == 0) 5 { 6 x = 1; 7 y = 0; 8 d = a; 9 }else10 {11 ExtendedEuclid(b,a%b,d,x,y);12 tmp = x;13 x = y;14 y = tmp - (a / b) * y;15 }16 }
应用
1.求解不定方程
2.求解模的逆元
3.求解同余方程