扩展欧几里得：
a和b的最大公约数可以根据欧几里得算法求解，得到了GCD。那么，必定存在x和y，使得ax+by=GCD。一个方程两个未知数，这是一个不定方程，存在多组解。欧几里得算法，即辗转相除算法停止的状态是：a=GCD,b=0。由此，我们可以联想到扩展欧几里得的最终状态上，即有a=GCD,b=0。那么此时x和y该为何值呢？x必定等于1，因为后一项不论y取何值，by已经等于0 了。但是，我们还是要让y=0。因为可以通过欧几里得算法可以想到这是一个递归的过程，那么x和y也是递归的，回调的时候为了方便计算，同时出于最简化的目的，这里的y也就等于0 了。那么就得到了：a*1+b*0=GCD。
假设刚开始的计算状态是：
ax+by=GCD//作为等式1。
那么按照欧几里得算法的思想，下一步的状态就应该是：
bx1+(a%b)y1=GCD//作为等式2。
然后一直递归知道a=GCD,b=0。然后在回调，假设已经得到了x1和y1。那么我们就可以得到等式1与等式2之间的计算关系。因为：
a%b=a-(a/b)*b//作为等式3，
代入等式2就有：
GCD=b*x1+(a-(a/b)*b)*y1=b*x1+a*y1-(a/b)*b*y1=a*y1+b*(x1-a/b*y1)
即有：
a*y1+b*(x1-a/b*y1)=GCD//作为等式4
与等式1相互对比可得到：
x=y1;y=x1-a/b*y1;//则这两个式子便是递推关系了。
给出代码：
<span style="font-size:18px;"><strong>ll Extended_Euclid(ll a,ll b,ll &x,ll &y)//ll long long
{
int d;
if(b==0)
{
x=1;y=0;//最终状态
return a;
}
d=Extended_Euclid(b,a%b,x,y);
ll temp=x;//递推关系
x=y;
y=temp-a/b*y;
return d;//返回值依旧还是GCD
}</strong></span>那么扩展欧几里得有什么用呢？可以用来求乘法逆元哦。
对于下面用到的同余基础知识不清楚的，可以传送去这里先看看：同余关系及其部分基本性质
什么就做乘法逆元？
逆元 ：(b/a) (mod m) = (b * x) (mod m)。 x表示a的逆元。并且 a*x ≡ 1 (mod m ) 注意：只有当a与m互质的时候才存在逆元。x叫做a关于n的乘法逆元。
因为(b/a) (mod m) = (b * x) (mod m)，那么我们总可以找到p,q，使得
b/a-mp=bx-mq
两边同乘a/b，就可以得到1-m(ap/b)=ax-m(aq/b)。就有a*x ≡ 1 (mod m )成立。等同于式子：
a*x+m*y=1//作为等式5。
为什么要互质才能存在解？因为不互质的话，无论如何取值，最小差值为2，怎么可能让左边的2等于右边的1。所以互质情况下才会存在解。就是说GCD(a,m)!=1的时候无解。这也是a*x+b*y=c有解的充要条件：c%GCD(a,b)==0。约掉之后就变为了最简的形式，保证互质。
例：5关于模14的乘法逆元是多少？
5*x≡1(mod14)
14=5*2+4;
5=4*1+1;
所以：1=5-4=5-(14-5*2)=3*5-14
得到：5关于模14的乘法逆元是3。
理解这个过程有助于理解上述代码里面的回调过程。
上面已经说了求乘法逆元相当于等式5中的x。那么这一切就变得简单了，代码依旧是上一段代码，只不过GCD=1。因为传参的时候&x，所以回调完成的时候就可以得到乘法逆元了。
问题来了，求乘法逆元有什么用处？哈哈，中国剩余定理里面可是用到了哦！