欧几里德定理： 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,则逆元存在。
