eg：求5关于模14的乘法逆元
14 = 5*2+4
5 = 4*1+1
说明5与14互素，存在5关于14的乘法逆元
1 = 5-4 = 5-（14-5*2）= 5*3-14
因此5关于模14的乘法逆元为3
a存在模b的乘法逆元的充要条件是gcd（a,b）= 1
互质：两个数的最大公约数为1，则称这两个数互质，也叫互素
对于扩展欧几里得算法求乘法逆元的步骤解析。
设a>b
显然当b=0,gcd(a,b)=a.
此时x=1，y=0
当ab!=0时
设a*x1+b*y1 = gcd(a,b)
b*x2+(a mod b)*y2 = gcd(b,a mod b)
因为 gcd(a,b) = gcd(b,a mod b)
所以 a*x1+b*y1 = b*x2+(a mod b)*y2
继续写就是
a*x1+b*y1 = b*x2+(a-(a/b)*b)*y2 = a*y2+b*x2-(a/b)*b*y2
代码模板
int kzojld(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=kzojld(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return r;
}
