“ Ctrl AC！一起 AC！”
声明：本博客主要记录结论，证明较少，需要证明自行转往扩展欧几里得算法
目录
1.基本的扩展欧几里得算法
扩展欧几里得算法用来解决这样一个问题：给定两个非零整数a和b，求一组整数解（x，y），
使得ax+by=gcd(a,b)。
int exGcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
return a;
}
int g=exGod(b,a%b,x,y);
int temp=x;
x=y;
y=temp-a/b*y;
return g;
}
2.ax+by=c的求解
ax+by=c存在解的充要条件是c%gcd==0，且一组解（x，y）等于
? ?
其中（x0,y0)是一对已知的解（可通过ax+by=gcd(a,b）算出）
3.同余式
?(mod m)的求解
同余式：对整数a,b,m来说，如果m能整除a-b（即（a-b)%m==0)），那么就说a与b模m同余。
对应的同余式：ab(mod m)
根据同余式的定义有（a-b）%m=0，那么存在整数y使得ax-c=my，移项令y=-y后得：
ax+my=c
4.逆元的求解以及（b/a）%m的计算
1.求a模m的逆元，就是求解同余式ax??1(mod m)
右式的1就是上面结论3的c，要求c%gcd(a,m)等于零，也就是gcd（a，m）要等于1
费马小定理也可以求乘法逆元！！！
?感谢阅读！！！
“ Ctrl AC！一起 AC！”