* 拓展欧几里得算法

欧几里德定理： gcd(a, b) = gcd(b , a%b)
欧几里德算法停止的状态是： a= gcd ， b = 0

因为，这时候 a = gcd 的系数是 1 ，那么只要 b 的系数是 0 ，这时，我们就会有： a*1 + b*0 = gcd；

假设我们已经求出了下一个状态：b 和 a%b 的最大公约数，并且求出了一组x1和y1使得： b*x1 + (a%b)*y1 = gcd， 那么这两个相邻的状态之间是否存在一种关系呢？

1. b*x2 + (a%b)*y2 = gcd(b,(a%b))                                   
2. a*x1 + b*y1= gcd(a,b)
3. gcd(a, b) = gcd(b , a%b)

可得 b*x2+(a-a/b*b)y2=a*x1+b*y1  =>  b(x2-a/b*y2)+a(y2)=a*x1+b*y1

>>> 由a，b相等可知：
x2-a/b*y2=y1
y2=x1

于是代码就来了：

// a*x+b*y=gcd(a,b)
int ex_gcd(int a,int b,int &x,int &y){
    int t;
    if(b==0){
      // a*1 + b*0 = gcd；
      x=1;
      y=0;
      return a;
    }
    int gcd=ex_gcd(b,a%b,x,y);
    t=x;
    x=y;
    y=t-a/b*y;
    return gcd;
}

基于该独立可以得到所有满足ax+by=c的解：

x'=x+b/gcd*K
y'=y-a/gcd*K

然后还可以去求逆元：

ax=c(mod m)
ax-my=c
将y用-y替换就OK

如果c%gcd(a,m)=0,则逆元存在。