乘法逆元

· · 学习·文化课

若ax\equiv 1\pmod b，则x称为a关于mod\ b的乘法逆元，记作a^{-1}

利用扩展欧几里得算法，我们可以求得乘法逆元，因为求解ax\equiv 1\pmod b,a\perp b与求解下式等价

ax+by=1=gcd(a,b)

从上式可以看出，当且仅当a\perp b时，a存在关于mod\ b的乘法逆元。

利用乘法逆元，可以解解线性同余方程

ax\equiv r\pmod b,a\perp b

解即为x=a^{-1}r\mod b

1. 欧拉定理+快速幂法求逆元

解线性同余方程还有欧拉定理+快速幂法。

a\perp m,\text{则}a^{-1}\equiv a^{\varphi(m)-1}\pmod m

2. 逆元递推式

逆元递推式可以O(n)求1...n(mod\ b)的逆元

令b=n\lfloor\frac bn\rfloor+r，有r=b\ mod\ n

n\lfloor\frac bn\rfloor+r\equiv 0\pmod b r=-n\lfloor\frac bn\rfloor\pmod b

两边同乘n^{-1}r^{-1}得

n^{-1}\equiv-r^{-1}(\lfloor\frac bn\rfloor)=-(b\ mod\ n)^{-1}(\lfloor\frac bn\rfloor)\pmod b

因为b\ mod\ n<n，所以通过调用之前求过的逆元就可以求出n的逆元

用上述方法也可以递归求解单个数的逆元，时间复杂度稍高，为O(n^{\frac 13})

3. 前缀积法求逆元

前缀积法可以在O(n+\log b)求任n个数(mod\ b)的逆元

s_n^{-1}=(a_1a_2...a_n)^{-1}=a_1^{-1}a_2^{-1}...a_n^{-1}

易得a_{k+1}^{-1}=s_ks_{k+1}^{-1}

而s_k^{-1}=s_{k+1}^{-1}a_{k+1}

就可以求出所有数的逆元。

【练习】

Luogu P3811 逆元递推式模板题

Luogu P5431 快读模板题

从来不卡常的Nash学会了写快读...

Luogu P2054 快速乘模板题

这数学题真多模板