-
【乘法逆元】看这一篇就够了！乘法逆元的证明、详解及应用。
2025-05-18 21:43:10
本文章为乘法逆元详解。
前一到二节属于前置知识：同余。
乘法逆元的讲解从第三节开始。
一、同余运算
(
a
+
b
)
m
o
d
m
=
[
(
a
m
o
d
m
)
+
(
b
m
o
d
m
)
]
m
o
d
m
(a+b)\bmod m=[(a\bmod m)+(b\bmod m)]\bmod m
(a+b)modm=[(amodm)+(bmodm)]modm
(
a
−
b
)
m
o
d
m
=
[
(
a
m
o
d
m
)
−
(
b
m
o
d
m
)
+
m
]
m
o
d
m
(a-b)\bmod m=[(a\bmod m)-(b\bmod m) + m]\bmod m
(a−b)modm=[(amodm)−(bmodm)+m]modm
(
a
×
b
)
m
o
d
m
=
[
(
a
m
o
d
m
)
×
(
b
m
o
d
m
)
]
m
o
d
m
(a\times b) \bmod m = [(a \bmod m) \times (b \bmod m)] \bmod m
(a×b)modm=[(amodm)×(bmodm)]modm
(
a
÷
b
)
m
o
d
m
≠
[
(
a
m
o
d
m
)
÷
(
b
m
o
d
m
)
]
m
o
d
m
(a\div b) \bmod m ≠ [(a \bmod m) \div (b \bmod m)] \bmod m
(a÷b)modm=[(amodm)÷(bmodm)]modm
如：
(
12
÷
3
)
m
o
d
6
=
4
≠
(
12
m
o
d
6
)
÷
(
3
m
o
d
6
)
(12\div3) \bmod 6 = 4 ≠ (12 \bmod 6) \div (3 \bmod 6)
(12÷3)mod6=4=(12mod6)÷(3mod6)
二、同余性质
若
a
≡
b
(
m
o
d
m
)
a \equiv b\pmod m
a≡b(modm)，则
m
∣
(
a
−
b
)
m|(a-b)
m∣(a−b)。
同加性，若
a
≡
b
(
m
o
d
m
)
a\equiv b\pmod m
a≡b(modm)，则
a
+
c
≡
b
+
c
(
m
o
d
m
)
a+c \equiv b+c \pmod m
a+c≡b+c(modm) 。
同乘性，若
a
≡
b
(
m
o
d
m
)
a \equiv b \pmod m
a≡b(modm)，则
a
c
≡
b
c
(
m
o
d
m
)
ac \equiv bc \pmod m
ac≡bc(modm) 。
逆性质：若
a
c
≡
b
c
(
m
o
d
m
)
ac \equiv bc \pmod m
ac≡bc(modm) ，且
gcd
(
c
,
m
)
=
1
\gcd(c,m)=1
gcd(c,m)=1，有
a
≡
b
(
m
o
d
m
)
a \equiv b \pmod m
a≡b(modm)。
证明：
a
c
−
p
m
=
b
c
−
q
m
ac-pm=bc-qm
ac−pm=bc−qm ，
(
a
−
b
)
c
=
(
p
−
q
)
m
(a-b)c=(p-q)m
(a−b)c=(p−q)m，
c
c
c 与
m
m
m 互质，证明
a
−
b
a-b
a−b 为
m
m
m 的倍数，则
a
≡
b
(
m
o
d
m
)
a \equiv b \pmod m
a≡b(modm)。
同幂性：若
a
≡
b
(
m
o
d
m
)
a\equiv b\pmod m
a≡b(modm)，则
a
c
≡
b
c
(
m
o
d
m
)
a^c\equiv b^c\pmod m
ac≡bc(modm)。
三、乘法逆元
对于任意整数
a
a
a 而言，如果
a
a
a 和
p
p
p 互质，存在一个整数
x
x
x 使得
a
×
x
≡
1
(
m
o
d
p
)
a\times x \equiv 1\pmod p
a×x≡1(modp) ，则有：
b
÷
a
m
o
d
p
=
b
÷
a
×
(
a
×
x
)
m
o
d
p
=
b
÷
(
a
×
a
)
×
x
m
o
d
p
=
b
×
x
m
o
d
p
\begin{aligned} b\div a\bmod p&=b\div a\times(a\times x)\bmod p \\&=b\div (a\times a)\times x\bmod p\\&=b\times x\bmod p \end{aligned}
b÷amodp=b÷a×(a×x)modp=b÷(a×a)×xmodp=b×xmodp
x
x
x 为
a
a
a 在模
p
p
p 意义下的乘法逆元，写作
a
−
1
a^{-1}
a−1。
我们可以借此解决运算法则四遇到的问题。
例如：
2
×
5
≡
1
(
m
o
d
9
)
2\times 5 \equiv 1\pmod 9
2×5≡1(mod9)，则
5
5
5 是
2
2
2 关于模
9
9
9 的乘法逆元。所以
8
÷
2
m
o
d
9
=
8
×
5
m
o
d
9
=
4
8\div2\bmod9=8\times5\bmod9=4
8÷2mod9=8×5mod9=4。
有了乘法逆元之后，
b
÷
a
m
o
d
p
b\div a\bmod p
b÷amodp，如果
a
，
p
a，p
a，p 互质，那么就有：
b
÷
a
m
o
d
p
=
(
b
m
o
d
p
×
a
−
1
m
o
d
p
)
m
o
d
p
b\div a\bmod p=(b\bmod p\times a^{-1}\bmod p)\bmod p
b÷amodp=(bmodp×a−1modp)modp
四、如何求乘法逆元
1.费马小定理
费马小定理：若
p
p
p 是质数，对任意整数
a
a
a 不是
p
p
p 的倍数，有
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1}\equiv 1\pmod p
ap−1≡1(modp)，也可以写作
a
p
≡
a
(
m
o
d
p
)
a^{p}\equiv a\pmod p
ap≡a(modp)。
证明：根据同余的性质，
a
,
2
a
,
3
a
…
…
,
(
p
−
1
)
a
a,2a,3a……,(p-1)a
a,2a,3a……,(p−1)a 分别
m
o
d
p
\bmod p
modp 的结果各不相同。那么：
a
×
2
a
×
3
a
…
…
×
(
p
−
1
)
a
≡
1
×
2
×
3
…
…
×
(
p
−
1
)
(
m
o
d
p
)
a
p
−
1
×
[
1
×
2
×
3
…
…
×
(
p
−
1
)
]
≡
1
×
2
×
3
…
…
×
(
p
−
1
)
(
m
o
d
p
)
a
p
−
1
≡
1
(
m
o
d
p
)
\begin{aligned}a\times2a\times3a……\times(p-1)a&\equiv 1\times2\times 3……\times(p-1)\pmod p\\a^{p-1}\times[1\times2\times 3……\times(p-1)]&\equiv1\times2\times 3……\times(p-1)\pmod p\\a^{p-1}&\equiv 1\pmod p\end{aligned}
a×2a×3a……×(p−1)aap−1×[1×2×3……×(p−1)]ap−1≡1×2×3……×(p−1)(modp)≡1×2×3……×(p−1)(modp)≡1(modp)
如何求乘法逆元： 若
p
p
p 是质数，则有
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1}\equiv 1\pmod p
ap−1≡1(modp)，而
a
×
x
≡
1
(
m
o
d
p
)
a\times x\equiv 1\pmod p
a×x≡1(modp)，所以
a
p
−
2
a^{p-2}
ap−2 是
a
a
a 模
p
p
p 意义下的的乘法逆元。
可以用快速幂，时间复杂度为
O
(
log
p
)
O(\log p)
O(logp)。
2.快速求阶乘逆元
a
(
n
−
1
)
!
≡
a
n
!
×
n
(
m
o
d
p
)
[
(
n
−
1
)
!
]
−
1
≡
(
n
!
)
−
1
×
n
(
m
o
d
p
)
\begin{aligned} a\over{(n-1)!}&{\equiv} {{a}\over{n!}}\times n{\pmod p}\\ [(n-1)!]^{-1}&\equiv (n!)^{-1}\times n\pmod p\end{aligned}
(n−1)!a[(n−1)!]−1≡n!a×n(modp)≡(n!)−1×n(modp)
i
n
v
[
n
]
inv[n]
inv[n] 表示
n
n
n 的阶乘在模
p
p
p 意义下的的乘法逆元
(
n
<
p
)
(n
(n
i
n
v
[
n
−
1
]
≡
i
n
v
[
n
]
×
n
inv[n-1]\equiv inv[n]\times n
inv[n−1]≡inv[n]×n。
可以先用费马小定理先求出
i
n
v
[
n
]
inv[n]
inv[n]，接着推出所有逆元。
3.快速求连续自然数逆元
假设已知
i
=
1
i=1
i=1 的逆是
1
1
1。递推求
i
>
1
i>1
i>1 时的逆。
设
k
k
k 是
p
÷
i
p\div i
p÷i 的商，
r
r
r 是
p
÷
i
p\div i
p÷i 的余数，则
k
×
i
+
r
≡
0
(
m
o
d
p
)
k\times i+r\equiv 0\pmod p
k×i+r≡0(modp)；
在等式两边同乘
i
−
1
×
r
−
1
i^{-1}\times r^{-1}
i−1×r−1，得到
k
×
r
−
1
+
i
−
1
≡
0
(
m
o
d
p
)
k\times r^{-1}+i^{-1}\equiv 0\pmod p
k×r−1+i−1≡0(modp)；
移项得到
i
−
1
≡
−
k
×
r
−
1
(
m
o
d
p
)
i^{-1}\equiv -k\times r^{-1}\pmod p
i−1≡−k×r−1(modp)，即
i
−
1
≡
−
⌊
p
i
⌋
×
r
−
1
(
m
o
d
p
)
i^{-1}\equiv -\lfloor{{p}\over{i}} \rfloor\times r^{-1}\pmod p
i−1≡−⌊ip⌋×r−1(modp)；
最后右边加上
p
p
p ，得到
i
−
1
≡
p
−
⌊
p
i
⌋
×
r
−
1
(
m
o
d
p
)
i^{-1}\equiv p-\lfloor{{p}\over{i}} \rfloor\times r^{-1}\pmod p
i−1≡p−⌊ip⌋×r−1(modp)。
下面是洛谷 P3811 乘法逆元 的部分代码：
long long inv[maxn];
void inverse(long long n, long long p){
inv[1] = 1;
for(int i = 2; i <= n; ++i)
inv[i] = (p - p/i) * inv[p % i] % p;
}
4.非连续数字快速求逆元
设有
n
n
n 个非连续数字，快速求逆元。
仍然使用快速幂，复杂度为
O
(
n
log
n
)
O(n\log n)
O(nlogn)，并非最优。
设：
非连续数字为
a
1
，
a
2
，
a
3
…
…
a
n
a_1，a_2，a_3……a_n
a1，a2，a3……an；
s
[
i
]
=
a
1
×
a
2
×
…
…
×
a
i
s[i]=a_1\times a_2\times ……\times a_i
s[i]=a1×a2×……×ai；
e
[
i
]
=
a
n
×
a
n
−
1
×
…
…
×
a
i
e[i]=a_n\times a_{n-1}\times……\times a_i
e[i]=an×an−1×……×ai；
I
N
V
=
(
a
1
×
a
2
×
…
…
×
a
n
)
INV=(a_1\times a_2\times ……\times a_n)
INV=(a1×a2×……×an)的逆元。
则
i
n
v
[
i
]
=
I
N
V
×
s
[
i
−
1
]
×
e
[
i
+
1
]
inv[i]=INV\times s[i-1]\times e[i+1]
inv[i]=INV×s[i−1]×e[i+1]。
这样可以
O
(
n
)
O(n)
O(n) 得到所有数的逆元。
五.结束