参考
贝祖定理：如果a b是整数，那么一定存在整数x y使得ax+by=gcd（a,b)
即如果ax+by=c有解，那么c一定是gcd的倍数（c一定能整除gcd，c%gcd==0）
如果ax+by=1有解，那么gcd(a,b)=1.
xldch辗转相除求a b的最大公约数
gcd(a,b)=gcd(b,a%b)
int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b);}ax+by=gcd(a,b)有解
递归边界 当 b=0，a=gcd 函数返回的是a 即 a*1+b*0=gcd （1，0）为达到递归边界时的一组解
递归式 在递归的过程中gcd(a,b)=gcd(b,a%b) 即gcd不会随着递归层数的变化而变化
ax1+by1=gcd=bx2+(a%b)y2
联立 (a/b)*b+a%b=a 得到
x1=y2,y1=x2-(a/b)y2 此时就建立起了这层与下一层递归之间的关系，x1 y1是这层的解，x2，y2是下一层的解
// ax+by=gcdint exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;return a;}int g=exgcd(b,a%b,x,y);int x2=x,y2=y;x=y2;y=x2-(a/b)*y2;return g;}通过拓展xldch算法可以得到ax+by=gcd的一组解（x0，y0）可能为负数。那么如何通过特解求得通解
假设x0+s1,y0-s2为原方程的另一组解，则 联立 ax0+by0=gcd 得 a*s1=b*s2
s1/s2=b/a 因b/gcd与a/gcd互质 要想s1与s2取最小值，s1=b/gcd, s2=a/gcd
得到方程的通解为 x=x0+b/gcd*k y=y0-a/gcd*k k为整数
x的最wmdxn负整数解 (x%(b/gcd)+b/gcd)/(b/gcd)
如果gcd=1 即 a b互质，则可以将公式进行化简