gcd 与 egcd

gcd(a,b)是求解a，b的最大公因数，都比较熟悉了，直接上代码：

int gcd(int a, int b){
    if(b == 0)
      return a;
    else 
      gcd(b, a%b);
}

ax + by = gcd(a,b)
egcd算法是根据a,b同时求出x,y,gcd(a,b)
ax + by = gcd(a,b)
bx' + (a%b)y' = gcd(a,b)
a%b = a - (a/b)b
代入得：ay' + (x' - (a/b)y') = gcd(a,b)
而当b = 0时：a1 + b0 = a = gcd(a,b)
先上代码看一下：

int egcd(int a, int b, int &x, int& y){
    int d = a;
    if(d != 0){
      d = egcd(b,a%b,y,x);      //不太明白这里的x'，y'为什么等于上一步中的y，x
      y = (y - (a/b)*y);
    }else{
      x = 1;
      y = 0;
    }
    return 0;
}