学习笔记 - 数论/数学 - 乘法逆元

· · 个人记录

对于本篇文章，看这个就够了：https://oi-wiki.org/math/number-theory/inverse/

感觉本算法的应用比较广一些。 求法： | | | | | :- | :-: | -: | | 求 $i^{-1}\quad(1\le i\le n)$ | $\Theta(n)$ | [线性求从 1 开始连续 n 个数的逆元](https://oi-wiki.org/math/number-theory/inverse/#_5)| | 求 $i^{-1}\quad i \in s\ (s\subseteq[1,b]\,)$ | $\Theta(\left\vert s\right\vert+\log b)$ | [线性求任意 n 个数的逆元](https://oi-wiki.org/math/number-theory/inverse/#n) | | 求 $a^{-1}\quad \gcd(a,b)=1$ | $O(\log(\min(a,b)))$ | [扩展欧几里得法](https://oi-wiki.org/math/number-theory/gcd/#_7) | 求 $a^{-1}\quad \gcd(a,b)=1 $ 要求 $b \in \text{prime}$ |$\Theta(\log b)$ | [快速幂法](https://oi-wiki.org/math/number-theory/inverse/#_4) #不推荐| --- ## 线性求从 1 开始连续 n 个数的逆元 ### 先上结论： $$i^{-1}\equiv\begin{cases}\text{undifined},&i=0\\1,&i=1\\-\left\lfloor\dfrac p i \right\rfloor\cdot(p\bmod i)^{-1},&\text{otherwise}\end{cases}$$ ### 证明： $\because 1\cdot1=1\equiv1\pmod p\qquad\qquad\qquad\therefore 1^{-1}\equiv1\pmod p \because\left\lfloor\dfrac p i \right\rfloor\cdot i\,+\,(p\bmod i)\equiv0\pmod p\quad\therefore\left\lfloor\dfrac p i \right\rfloor\cdot(p\bmod i)^{-1}\,+\,i^{-1}\equiv0\pmod p

代码

void getInv(int n,int p){//get inv[1~n] (mod p)
    inv[1]=1;for(int i=2;i<=n;i++)
        inv[i]=(ll(p-p/i)*inv[p%i])%p;
}

线性求任意 n 个数的逆元

先通过一次扫描扫出 n 个数前缀乘积数组 S

然后通过扩展欧几里得法或快速幂法求出 S_n^{-1}

然后从后往前递推求出前缀逆元乘积数组 S^{-1}

依靠 a_i^{-1}=\dfrac{S_i^{-1}}{S_{i-1}} 求出 a^{-1}

代码

int s[5000005],r[5000005];  //r->s^{-1}
int* getInv(int* __first,int* __last,int p){
    s[0]=1;for(int i=1;i<=(__last-__first);++i)s[i]=(ll(s[i-1])**(__first+i-1))%p;
    int y;exgcd(s[__last-__first],p,r[__last-__first],y);r[__last-__first]=(r[__last-__first]%p+p)%p;
    for(int i=__last-__first;i>=1;i--)r[i-1]=(ll(r[i])**(__first+i-1))%p;
    for(int i=1;i<=__last-__first;i++)inv[i]=(ll(s[i-1])*r[i])%p;return inv+1;
}