问题描述：
a 和 b的最大公约数是多少？
古代解法：辗转相除法
迭代过程：例如：
{a = 15 和 b = 12 }
=>{ a = 12,b = 15 - (15/12)* 12 = 3 }
=> {a = 3,b= 12 - (12/3)*3 = 0 }
=> { b = 0 所以a为最大公因数}
c++代码:
int gcd(int a,int b){return b?gcd(b,a%b):a;}一行搞定。
实战： 对于平面坐标上的俩点 (x1,y1) 与(x2,y2) 他们之间的连线上有多少个点的坐标都是整数？（不包括给出的端点）
分析 ：我们初中就学过相似三角形,那么假如存在点p（x0，y0），那么 (y2-y1)/ (y0-y1) == (x2-x1)/(x0-x1)
变换一下形式 ： (y2-y1)/(x2-x1) ==(y0-y1) /(x0-x1) ， 这俩个分式的分子和分母都应该是整数，
那么假如左式不能约分，那么右式的分子分母应该等于左式地分子分母，
假如左式能约分 （假如约数有多个，即约完后又多种分式形式），那么右式的分子分母应该对应等于左式约分后对应的分子分母，所以约数的个数决定了解的个数。那么这题的解法就是 gcd( abs(x1-x2) , abs(y1-y2) ) -1
上述的问题与解答就是sxdsg原理。
下面我们再来看几个拓展的问题：
大家应该在高中学过二元一次不定方程对吧，那么对于 ax+by = c，的方程求整数解，
我们一般的解法都是找到一组特解，然后就很容易得到x = x0 + bt; y =y0 - at,其中t是整数 的这样的方程解
但是这样的效率是很低的，为什么呢？ 对于a b数字比较小的话，你可能花个几分钟能找出特解，但是当a和b是几千万甚至是超出了c++的最长整形数表示范围，那么你还打算暴力找特解吗？这样的时间花费是O（n）的。
所以我们从这个问题马上引出扩展sxdsg算法来求解二元一次方程：
对于ax+by = c ，我们认为约定好a>b哈（这个减少我们的讨论次数），那么由我们的sxdsg原理知道：
如果ax + by = c 有解，当且仅当gcd(a,b) 是 c 的倍数 为什么呢？
证明: https://blog.csdn.net/yoer77/article/details/69568676
如果 aa 和 bb 中有一个是 0，比如 a=0a=0，那么它们两个的最大公约数是 bb。这时wndwg等式变成 by=mby=m，它有整数解 (x,y) 当且仅当 mm 是 bb 的倍数，而且有解时必然有无穷多个解，因为 xx 可以是任何整数。定理成立。
以下设 a和 b 都不为0。
设 A={xa+yb;(x;y)∈Z2}A={xa+yb;(x;y)∈Z2} ，下面证明A中的最小正元素是 a 与 b 的最大公约数。
首先，A∩N∗A∩N∗ 不是空集（至少包含|a||a| 和|b||b|），因此由于自然数集合是良序的， AA 中存在最小正元素d0=x0a+y0bd0=x0a+y0b。考虑AA中任意一个正元素p（=x1a+y1b）p（=x1a+y1b）对 d0d0 的带余除法：设p=qd0+rp=qd0+r，其中 qq为正整数，0≤r<d00≤r<d0。但是
r=p−qd0=x1a+y1b−q(x0a+y0b)∈Ar=p−qd0=x1a+y1b−q(x0a+y0b)∈A
而d0d0 已经是集合 AA 中最小的正元素了，又 0≤r<d00≤r<d0,所以 r=0r=0。
因此 d0 | pd0 | p。也就是说，A中任意一个正元素p都是 d0d0 的倍数，特别地：d0 | a、d0 | bd0 | a、d0 | b。因此 d0d0 是 aa 和 bb 的公约数。
另一方面，对 a 和 b 的任意正公约数dd，设 a=kd、b=lda=kd、b=ld，那么
d0=x0a+y0b=(x0k+y0l)dd0=x0a+y0b=(x0k+y0l)d
x0k+y0l≥1x0k+y0l≥1 ,因此 d | d0d | d0。所以 d0d0 是 aa 和 bb 的最大公约数。
在方程ax+by=max+by=m中，如果 m=m0d0m=m0d0，那么方程显然有无穷多个解：
相反的，如果ax+by=max+by=m有整数解，那么 |m|∈A|m|∈A，于是由前可知 d0 | |m|d0 | |m|（即 d0 | md0 | m）。
m=1时，方程有解当且仅当a、b互质。方程有解时，解的集合是
其中 (x0,y0)(x0,y0) 是方程ax+by=d的一个解，可由辗转相除法得到。
所有解中，有且仅有一个解(x,y) 满足 −b≤x≤b，−a≤y≤a
下面我们来证明一下扩展sxdsg的递归过程：（先贴出代码）
int ex_gcd(int a,int b,int &x,int &y){if(b == 0){x = 1;y = 0;return a;}else{int r = ex_gcd(b,a%b,y,x);int t = y;y = x - (a/b)*y;x = t;return r;}}我们给出递归的证明：
给定一个方程解 ：a * x1 + b * y1 = gcd(a,b) 由sxdsg原理=> b*x2 + (a%b)*y2 = gcd(b,a%b)
因为gcd(a,b) = gcd(b,a%b),所以，俩等式左侧相同，得到：
ax1+by1 = bx2 + ( a - (a/b) * b )*y2
=> ax1 + by1 = ay2 + b(x2 - a/b * y2) ......(对等原理)
=> x1 = y2 , y1 = x2 - a/b * y2 ,
那么递归的上层x1 y1 均依赖于 上层的a，b和下层的x2，y2，所以递归回溯得到的 x2 和 y2 可以求出当前层的 x1 y1
直到回溯结束。
那么递归的底层结束条件是什么呢？ 我们发现sxdsg原理的结束条件是b == 0 ，而扩展sxdsg 的x y系数是sxdsg原理的方法，所以递归到底层的时候一次能够会出现b==0 的情况 ，这个时候方程变为 ax = a 所以 此时解为 x = 1 ，y = 0
然后一直回溯，最后就能求出x y的解了