乘法逆元

乘法逆元

线性同余方程\(ax\equiv1(mod\,b)\)

此时称\(x\)为\(a\)在\(mod\,b\)意义下的逆元，记作\(a^{-1}\)

求法

1. \((a,b)=1\)

可用扩展欧几里得算法（exgcd），求\(xa+yb=1\)的解即可

2. \((a,b)=1\)且b为质数

\(ax\equiv1\equiv{a^{b-1}}(mod\,b)\)

\(x\equiv{a^{b-2}}\)

可用快速幂

3. 线性求逆元

1~n

这里指的是1到n的逆元一起求，显然用之前的方法会有可能超时

这里用递推式解决

设求1到n在\(mod\,p\)的逆元，p是大质数

\(p=ki+j,k=\frac{p}{i},j=p\,mod\,i\)

则有\(ki+j\equiv0(mod\,p)\)

同乘\(i^{-1}\times{j^{-1}}\)

得到\(i^{-1} \equiv-k j^{-1}(\bmod p)\)

即\(i^{-1} \equiv-\left\lfloor\frac{p}{i}\right\rfloor(p \bmod i)^{-1}(\bmod p)\)

考虑到\(p\,mod\,i<i\)，可以用递推解决 \[ i^{-1}\equiv\left\{ \begin{array}{**lr**} 1,&if\,i=1\\ -[\frac{p}{i}](p\,mod\,i)^{-1},&otherwise. \end{array} \right.\;\;\;\;\;(mod\;p) \] 代码

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}

任意n个数的逆元

可以用前缀积去处理

假设我们要求\(A=\{a_1,a_2,...,a_n\}\)的逆元

我们处理出前缀积\(S=\{s_1,s_2,...,s_n\}\)

求\(s_n\)的逆元\(sv_n\)，\(sv_n\)乘\(a_n\)为\(sv_{n-1}\)，同理处理出所有\(sv_i\)

故\(a_i^{-1}=sv_i*s_{i-1}\)

代码

s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = qpow(s[n], p - 2);
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;