2023-07-29 16:22:14
辗转相除法 (求gcd)
求 \(a,b\) 的最大公约数。
假设 \(a\ge b\) ，令 \(gcd(a,b)=d\)（下文都这样表示）。
那么设 \(a=k_1d\),\(b=k_2d\)，则 \(a\mod b =(k_1-rk_2)d\)，当 \(k1-rk2>0\) 时，满足 \(gcd(a,b)=gcd(a,a\mod b)\)；当\(k1-rk2=0\)，\(gcd(a,b)=b\)（\(a\) 被 \(b\) 整除）。
所以求 \(gcd(a,b)\) 的代码可表示为:
inline int gcd(a,b){
if(!b)return a;//被整除
return gcd(b,a%b);
}
复杂度分析
下文均用 \((a,b)\) 表示 \(gcd(a,b)\)。
当 \(a>b\) 时，若 \(a< 2b\)，那么 \(a\mod b =a-b < \left\lfloor \dfrac{a}{2}\right\rfloor\)。
若 \(a\ge 2b\)，\(a\mod b =a-r\times b < \left\lfloor \dfrac{a}{2}\right\rfloor\)。
综上，\(a\mod b <\left\lfloor \dfrac{a}{2}\right\rfloor\)。
那么每次取余都会使数减小至少一半，所以求 \((a,b)\) 时间复杂度 \(O(\log_2 ab)\)。
exGCD（扩展欧几里得定理）
结论1：
若 \((a, b) = 1\)，则必然存在整数 \(x\) 使得 \(ax \equiv 1(\mod b)\)。
证明:
先证明结论2：\(\forall x, 0<x<b,ax \mod b\) 互不相同。
我们用反证法：
假设 \(\exists x_1,x_2, 0<x1<x2<b,ax_1\equiv ax_2 (\mod b)\)。
那么 \(a(x_2-x_1)\equiv 0(\mod b)\)，即\(b|(x_2-x_1)\)，而 \(0<x1<x2<b\)，与假定条件不符，故不存在 \(x_1,x_2\) 满足条件。
因为其互不相同，且 \(x\ne0\)，那么 \(ax \mod b \in [1,b-1]\)，则肯定存在 \(x\) 使得 \(ax \equiv 1(\mod b)\)。
推论1
若 \((a, b) = 1\)，则必存在整数 \(x, y\) 满足 \(ax + by = 1\)。
这个就是直接把取模变成减 \(b\)，这里不予证明。
裴蜀定理
在推论1中是 \(a,b\) 互质的情况，我们把它推广到一般情况。
对于整数 \(a, b\)，存在整数 \(x, y\) 满足 \(ax + by = (a, b)\)。
证明:
令 \((a,b)=d\)，则我们可得： \(\dfrac{a}{d}\ x + \dfrac{b}{d}\ y = 1\)，此时 \((\dfrac{a}{d},\dfrac{b}{d})\) 互质，满足推论1的形式，故得证。
如何求出一组整数解 \(x,y\) ？
可以通过类似求 \((a,b)\) 的方法，通过子答案的解来推出现在的解。
推式子：
\(ax+by=(a,b)\)
\((a\mod b +\lfloor\dfrac{a}{b}\rfloor\times b)\ x+by=(a,b)\)
\((\lfloor\dfrac{a}{b}\rfloor\ x+y)b+(a\mod b)x=(a,b)\)
那么我们就得到了：
\(bx'+(a\mod b)y'=(a,b)\)
是不是很熟悉，此时的 \(x=y',y=x'-\lfloor\dfrac{a}{b}\rfloor\ y'\)。
当 \(b=0\) 时，\((a,b)=a\),那么我们可以得到其中一组解 \((x,y)\) 为 \((1,0)\)。
代码实现:
inline void ex_gcd(int a,int b,int &x,int &y){
if(!b)return x=1,y=0,void();
ex_gcd(b,a%b,y,x);
y-=a/b*x;//注意指代，此时的y=x',x=y',所以按着上面的公式应该这样转移答案
}
中国剩余定理（CRT）
逆元
\(a\times a^{-1}= 1\)，我们称 \(a^{-1}\) 为 \(a\) 的逆元。
若\(a^{-1}\equiv x (\mod p)\)，我们称 \(x\) 为 \(a\) 模 \(p\) 意义下的逆元。
\(\color {red} {注意：当\ (a,p)\ne 1\ 时，不存在逆元}\)。
应用：
由于取模之后不能进行除法操作，所以我们可以通过将除数求逆元再与被除数相乘的方式来实现取模下的除法操作。
exGCD求逆元
使用条件：\((a,p)=1\)。
\(ax\equiv 1(\mod b)\)，即 \(x\) 是 \(a\) 模 \(p\) 意义下的逆元。
那其实就是求 \(ax+by=1\) 的解。
注意答案的 \(x\) 可能为负数，所以我们要稍微修改一下。
代码实现
inline void ex_gcd(...){...}
inline inverse(int a,int p){//模p意义下的逆元
int x,y;
ex_gcd(a,p,x,y);
return (x%p+p)%p;
}
快速幂求逆元
费马小定理：\(a^{p-1}\equiv 1(\mod p)\)
\(a\times a^{p-2}\equiv 1(\mod p)\)
所以 \(a^{p-2}\) 即为所求。
因为原理是根据费马小定理得到，所以：
\(\color {red}{使用条件：当p是与a互质的质数。}\)
代码就是快速幂代码：
ll qpow(ll a,ll x){
ll res=1;
for(;x;x>>=1,a=a*a%p)if(x&1)res=res*a%p;
return res;
}
ll inverse(ll a){
return qpow(a,p-2);
}
线性求逆元
以下内容因为字数太多作者不想打，所以这一部分转载于 \(OIwiki\)。
求出 \(1,2,\dots,n\) 中每个数关于 \(p\) 的逆元。
如果对于每个数进行单次求解，以上两种方法就显得慢了，很有可能超时，所以下面来讲一下如何线性（\(O(n)\)）求逆元。
首先，很显然的 \(1^{-1} \equiv 1 \pmod p\)；
证明
对于 \(\forall p \in \mathbf{Z}\)，有 \(1 \times 1 \equiv 1 \pmod p\) 恒成立，故在 \(p\) 下 \(1\) 的逆元是 \(1\)，而这是推算出其他情况的基础。
其次对于递归情况 \(i^{-1}\)，我们令 \(k = \lfloor \frac{p}{i} \rfloor，j = p \bmod i\)，有 \(p = ki + j\)。再放到 \(\mod p\) 意义下就会得到：\(ki+j \equiv 0 \pmod p\)；
两边同时乘 \(i^{-1} \times j^{-1}\)：
\(kj^{-1}+i^{-1} \equiv 0 \pmod p\)
\(i^{-1} \equiv -kj^{-1} \pmod p\)
再带入 \(j = p \bmod i\)，有 \(p = ki + j\)，有：
\(i^{-1} \equiv -\lfloor\frac{p}{i}\rfloor (p \bmod i)^{-1} \pmod p\)
我们注意到 \(p \bmod i < i\)，而在迭代中我们完全可以假设我们已经知道了所有的模 \(p\) 下的逆元 \(j^{-1}, j < i\)。
故我们就可以推出逆元，利用递归的形式，而使用迭代实现：
\(i^{-1} \equiv \begin{cases} 1, & \text{if } i = 1, \\ -\lfloor\frac{p}{i}\rfloor (p \bmod i)^{-1}, & \text{otherwise}. \end{cases} \pmod p\)
实现
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}
使用 \(p-\lfloor \dfrac{p}{i} \rfloor\) 来防止出现负数。
另外我们注意到我们没有对 \(inv[0]\) 进行定义却可能会使用它：当 \(i | p\) 成立时，我们在代码中会访问 \(inv[p % i]\)，也就是 \(inv[0]\)，这是因为当 \(i | p\) 时不存在 \(i\) 的逆元 \(i^{-1}\)。线性同余方程中指出，如果 \(i\) 与 \(p\) 不互素时不存在相应的逆元（当一般而言我们会使用一个大素数，比如 \(10^9 + 7\) 来确保它有着有效的逆元）。因此需要指出的是：如果没有相应的逆元的时候，\(inv[i]\) 的值是未定义的。
另外，根据线性求逆元方法的式子：\(i^{-1} \equiv -kj^{-1} \pmod p\)。
递归求解 \(j^{-1}\), 直到 \(j=1\) 返回 \(1\)。
中间优化可以加入一个记忆化来避免多次递归导致的重复，这样求 \(1,2,\dots,n\) 中所有数的逆元的时间复杂度仍是 \(O(n)\)。
注意：如果用以上给出的式子递归进行单个数的逆元求解，目前已知的时间复杂度的上界为
\(O(n^{\frac 1 3})\)，具体请看 知乎讨论。算法竞赛中更好地求单个数的逆元的方法有扩展欧几里得法和快速幂法。