扩展欧几里得算法（乘法逆元、不定方程求整数解）
数 论 只 会 g c d
但 是 也 比 不 会 好
欧几里得算法（辗转相除法）
也就是$gcd(a,b)=gcd(b,a\%b)$
知乎上看到了一个比较好的证明（证明过程不重要）：
我们只需要证明a,b的公因数集等于b,a%b的公因数集，那么这两个集合里的最大值肯定也相等，即$gcd(a,b)=gcd(b,a\%b)$
设$a=bq+r$，要证明：若d是a和b的公因数，当且仅当d是b和r的公因数
1）设d是a和b的公因数，则d|a且d|b，于是d|(a-bq)，也就是d|r —> d是b，r的公因数
2）设d是b和r的公因数，则d|b且d|r，于是d|(bq+r)，也就是d|a —> d是a，b的公因数
综上，a,b的所有公因数和b,r的所有公因数是一样的。那么，d是a和b的最大公因数，当且仅当d是b和r的最大公因数，即$gcd(a,b)=d=gcd(b,a\%b)$
扩展欧几里得算法
这个算法说到底就是用来解决：求$ax+by=c$的整数解。
至于求乘法逆元之类的应用其实应该和算法本身是独立的，应该分开来讲。
先讲如何求解。
求解
首先根据裴蜀定理，这个方程有解，当且仅当$c\%gcd(a,b)=0$，或者说c是gcd(a,b)的整数倍。（裴蜀定理的证明放在后面，依然不重要）
不妨设$ax+by=gcd(a,b)$，由欧几里得算法，$gcd(a,b)=gcd(b,a\%b)$，
因此$ax+by=gcd(a,b)=gcd(b,a\%b)=bx’+(a\%b)y’$
这里求x，y的解需要利用递推的思想。假设已知上一层x’和y‘，如何推导出当前x，y的值？这里需要稍微手算一下。
把a%b写成a-a/b*b，于是得到$ax+by=bx’+(a-a/b*b)y’=ay’+b(x’-a/b*y’)$
通过计算得到$x=y’,y=x’-a/b*y’$
ok，现在已经找到了由上一层解推出当前层解的递推关系了，那么递推的出口在哪里呢？
由于每递归一层，a和b的变化是：a=b,b=a%b，就相当于做了一层辗转相除法。所以最终，当a=gcd,b=0时，这个方程就变成了
此时x=1，y=0就是一组特解（其实y也可以不为0，但是没必要，还可能导致爆int之类的）。找到解后就可以回溯，递推计算出每一层的x，y了。
于是顺便证明一下裴蜀定理（老证明癌了）：
充分性：若$c\%gcd(a,b)=0$的倍数，那么总是可以通过上面的扩欧算法求出一组整数解。
必要性：若$ax+by=c$存在整数解$ax_1+by_1=c$ (x1,y1为具体整数)，设d是a,b的最大公因数即d|a,d|b，于是d|(ax1+by1)，即d|c，$c\%gcd(a,b)=0$
证毕
扩欧板子
非常简洁的两行代码
void Exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) x = 1, y = 0;
else Exgcd(b, a % b, y, x), y -= a / b * x;
}
由于$ax+by=ax+ab+by-ab=a(x+b)+b(y-a)$，也就是$x’=x+b,y’=y-a$同样是方程的解
所以有时对x或y取值范围有要求（比如要求为正整数）就可以通过同时修改x和y来进行调整，比如说
Exgcd(a,b,x,y);
while(x<0) x+=b,y-=a;
或者直接写成
x = (x % b + b) % b;
应用
把扩欧算法讲清楚之后，具体怎么应用其实就要自己判断了。比如说比较常见的的通过扩欧求乘法逆元
求a在mod b意义下的逆元，即求$ax\equiv1(mod b)$
把这个式子化一下，其实就变成求$ax+by=1$中x的整数解的问题
根据裴蜀定理，这个不定方程有整数解的前提是gcd(a,b)=1，即a，b互质。（而保证互质的一个方法是令a或b为一个大质数，比如998244353或者1e9+7之类的，所以如果题目莫名给了一个大质数或者a，b互质的条件，很可能就是在保证扩欧方程有解的前提）
把a，b带入方程之后算出x，并调整x的范围即可。
void Exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) x = 1, y = 0;
else Exgcd(b, a % b, y, x), y -= a / b * x;
}
ll x, y;
Exgcd (a, p, x, y);
x = (x % p + p) % p;
printf ("%d\n", x); //x是a在mod p下的逆元
Fraction Construction Problem
有时题目要求计算$ax-by=c$，这时候只需要转化成$ax+b(-y)=c$，最后y取相反数就可以了。