定义：设a , b为常数，对于一个表达式 a \* x + b \* y =GCD( a , b ) ，一定存在解（ x , y）使之成立。 我们就可以通过扩展原来的辗转相除法来求解。 求解的过程如下（**最好自己手推一下**）： > 初始表达式 > `$ a * x + b * y =GCD( a , b ) $` > 由之前的知识可得 > `$ GCD( a , b ) =GCD( b , a \% b ) $` > 因此 > `$ a*x_1+b*y_1=GCD( a , b ) =GCD( b , a\%b ) =b*x_2+(a\%b)*y_2 $` > `$ a\%b=a-[a/b]*b $` > 其中\[a/b\]表示整除。带入化简可得： > `$ a*x_1+b*y_1=a*x_2+b*(x_2-[a/b])*y_2 $` > 由恒等关系可得 > `$ x_1=y_2 $` > `$ y_1=(x_2-[a/b]) $` > 因此我们只要求出 x2 和 y2 的值就可以求解 x1 和 y1。而 x2 , y2 可通过同种方法求解。 > > 特别的，当 b=0时，表达式为 a \* x + b \* y = GCD( a , b ) =GCD( a , 0 ) = 0 > > 此时,可求得 x = 1 。y 的值对表达式的值没有影响。 > > 上面就是求解初始表达式的方法。 代码如下： ~~~ int extGcd(int a,int b,int &x,int &y)//这里取 x , y的地址 {    if(b==0)   {        x=1;y=0;        return a;//函数的返回值一直是 gcd(a,b)   }    int r=exGcd(b,a%b,x,y);    int t=x; x=y;   //x1=y2 y=t-a/b*y; //y1=x2-[a/b]*b    return r; } ~~~