1.定义：扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式a x + b y = gcd ( a , b ) .(贝祖等式也叫贝祖定理，即给定二个整数a、b，必存在整数x、y使得ax + by = gcd(a,b)) 。
2.具体说一下，由ax+by=gcd(a,b)，可知，
当b=0的时候， gcd(a,b)=a，此时x=1，y=0为一组解。
当b!=0时，设ax1+by1=gcd(a,b)，由之前的辗转相除法可知 gcd(a,b)=gcd(b,a%b)，
设bx2+(a%b)y2=gcd(b,a%b)=gcd(a,b)， 则①bx2+(a%b)y2=ax1+by1
由之前的b=0时的式子已经知道了x2=1和y2=0，(假设a和a%b为最终状态)，那么我们需要知道x1 , y1，这个可以在函数递归返回的时候得到，而现在我们手头做的是递推的到解。
式子可以化为a%b=a-(a/b)*b(注意，a/b是向下取整且优先级第一)，将其带入①式，得到
b*x2+(a-(a/b)*b)*y2=ax1+by1
进而可以得到a*y2+b*y2=a*x1+b*y1，所以，在知道x2和y2 之后，可以推出②x1=y2 ,③y1=x2 – (a/b)*y2 ，逆向推导回去即可。
3.通解：式子ax+by=k*gcd(a,b)的通解(当k=1时就是上面的情况)，设ax0+by0=gcd(a,b)，则a(x0k)+b(y0k)=k*gcd(a,b)，那么其通解为x=x0k+t*b/gcd(a,b) , y=y0k-t*gcd(a,b)，t在计算中是可以消掉的
int ex_gcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
return a;
}
int r=ex_gcd(b,a%b,x,y);
int tmp=x;
x=y;//这是②式
y=tmp-(a/b)*y;//这是③式
return r;
}