逆元
克尔苏加德
·
·
个人记录
不会太多，就说说乘法逆元吧
\bullet 乘法逆元
$\qquad$ 若 $a \cdot x\equiv 1 (\mod b)$ 且 $a$ 与 $b$ 互质，那么我们就称 $x$ 为 $a$ 的逆元，记作 $a ^{-1}$ ,我们也可以称 $x$ 为 $a$ 在 $\mod b$ 意义下的逆元（当 $b = 1$ 时就是倒数）
$\qquad$所以对于 $\dfrac{a}{b} (\mod p)$ 我们就可以求出 $b$ 在$\mod p$ 下的逆元然后乘上 $a$ ，再$\mod p$ ，就是这个分数的值了
$\quad \mathbf{\large2}.\quad$求解逆元的方式
$\qquad \mathbf{1^\circ}$ **拓展欧几里得**
$\qquad\quad$ 是解 $a\cdot x \equiv c(\mod b)$ 的整数解 $(x,y)$ 而这个方程存在整数解的充分条件是 $\gcd(a,b) | c$ 即 $c$ 为 $a,b$ 最小公倍数的一个倍数
$\qquad\quad$ 下面来推一波拓欧
$\qquad\quad ax + by = \gcd(a,b)
\qquad$ 若已知 $ax+by = \gcd(b,a\mod b)
\qquad\quad\begin{matrix}\Updownarrow\\bx + (a\mod b)y = \gcd (b,a\mod b)\\\Downarrow\\bx+(a - \left\lfloor\dfrac{a}{b}\right\rfloor b)y = \gcd(b,a\mod b)\\\Downarrow\\ay + b(x - \left\lfloor\dfrac{a}{b}\right\rfloor*y) = \gcd(b,a\mod b)\end{matrix}
```cpp
void ex_gcd(LL a,LL b,LL &x,LL &y){
if(!b){
x = 1;
y = 0;
}
else {
ex_gcd(b,a % b,y,x);
y -= x * (a / b);
}
return ;
}
```
$\qquad \mathbf{2^\circ}$ **费马小定理**
$\qquad\quad$ 若 $p$ 为素数， $a$ 为正整数，且 $a,p$ 互质，则有 $a^{p - 1}\equiv1(\mod p)
\qquad\quad \begin{matrix}a\cdot x\equiv1(\mod p)\\\Updownarrow\\a\cdot x \equiv a^{p - 1}(\mod p)\\\Downarrow\\x\equiv a^{p -2}(\mod p)\end{matrix}
```cpp
LL qpow(LL a,LL b,LL p){
LL c = 1;
while(b){
if(b & 1) c = c * a % p;
a = a * a % p;
b >>= 1;
}
return c;
}
```
$\qquad\quad$ 如果 $c \neq 1$ 呢，可以运用欧拉定理：若 $a,p$ 互质，则 $a^{\varphi(p)}\equiv 1(\mod p)$ 这里 $\varphi(p)$ 需要预处理解出来，再结合快速幂就可以了
$\qquad\quad$ 如果 $a,p$ 不互质，用扩展欧拉定理，在这里就不补充了
$\qquad \mathbf{3^\circ}$ **线性递推**
$\qquad\quad$ 这种方法是用来求一连串数字对于一个 $\mod p$ 的逆元
$\qquad\quad$ 在处理一连串的时候，只能用这种方法，其他的都要比这个慢
$\qquad\quad$ 首先有 $ 1^{-1} \equiv 1(\mod p)
$\qquad\quad\begin{matrix}k*i+r\equiv0(\mod p)\\\\k*{r^{-1}} + i^{-1}\equiv 0(\mod p)\\\\i^{-1}\equiv -k*r^{-1}(\mod p)\\\\i^{-1} \equiv -\left\lfloor\dfrac{p}{i}\right\rfloor*(p\mod i)^{-1}(\mod p)\end{matrix}
\qquad\quad$ 这里用 $f$ 数组存储已经求出的逆元，所以 $p\mod i$ 的逆元即为 $f[p\mod i]
$\qquad\quad$ 最终得到 $\color{Red} i^{-1} \equiv p - \left\lfloor\dfrac{p}{i}\right\rfloor *(p\quad \mathrm mod \quad i)^{-1}(\mathrm mod\quad p)
void inv(LL n,LL p){
f[1] = 1;
for(int i = 2 ; i <= n ; i ++)
f[i] = p - (p / i) * f[p % i] % p;
}