目录
裴蜀定理
逆元并非对任何数存在……
定理：\(ax+by=c\) 有解 \(\{x,y\}\) 当且仅当 \(c\) 是 \(\gcd(a,b)\) 的倍数。
证明必要性：反证
假设 \(c\) 不是 \(\gcd(a,b)\) 的倍数。
设 \(d=\gcd(a,b)\)，将等式两边除以 \(d\) 可得： \(a\frac{x}d+b\frac{y}d=\frac{c}d\)
因为 \(d\mid a, d\mid b\)，所以 \(d\mid ax,d\mid by\)，就有 \(d\mid ax+by\)，说明等式左边是一个整数。
然而 \(c\) 不是 \(d\) 的倍数，所以右边不是整数。矛盾。
那么，这和逆元有什么关系呢？
哦，发现 \(\gcd(a,b)=1\) 的时候，方程变为 \(ax+by=1,ax=1-by\)，啊发现方程一定有解。
等式两边同时模 \(b\)，\(ax\% b= (1-by)\%b = 1\%b-by\%b\)，得到： \(ax\equiv 1\pmod b\)
艹，这不是逆元嘛……
而且根据裴蜀定理，发现 \(gcd(a,b)>1\) 时这个方程无解。
\(\gcd(a,b)=1\)，此时求出的 \(x\) 就是 \(a^{-1}\)
推论： \(ax\equiv 1\pmod b\) 有解当且仅当 \(a\) 与 \(b\) 互质（也记作 \(a\perp b\)）
例题：P4549，模板题
Exgcd 扩展欧几里得算法
此算法用于求解 \(ax+by=c\) 的解，其中 \((a,b)\mid c\)
此方法的基本思路已经在如下几篇文章里讲的很清楚了：
https://www.luogu.com.cn/blog/command-block/tong-yu-xi1
https://oi-wiki.org/math/number-theory/gcd/
得到一个求出全解的递推公式：
\(x_1=y_2;y_1=x_2-\lfloor \frac{a}{b} \rfloor y_2\)
如果不会，可以背板子
int Exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return d;
}
我们就可以用这个求逆元，\(ax+by=1\)
可是注意，这里的Exgcd算法并不是基于同余的算法，所以算出的结果可能是负数，啊我们只需要加上模数再模就能保证正数。即我们求出了 \(x\)，返回要(x+mod)%mod能够保证正数，其与x%mod(x>=0)是等价的。
例题：P5656，exgcd模板题
等我学会了……
标签：gcd,int,mid,Exgcd,逆元,ax,裴蜀 From： https://www.cnblogs.com/CYLSY/p/16819606.html