乘法逆元基础
可以使用扩展欧几里得算法或费马小定理求得。
乘法逆元进阶
有一种乘法逆元的线性递推算法：
显然
1
−
1
≡
1
(
m
o
d
m
)
1^{-1} \equiv 1 \pmod m
1−1≡1(modm)；
对于
i
−
1
i^{-1}
i−1，我们令
k
=
⌊
m
i
⌋
k = \lfloor \frac{m}{i} \rfloor
k=⌊im⌋，
j
=
m
m
o
d
i
j = m\bmod i
j=mmodi，有
m
=
k
i
+
j
m= ki + j
m=ki+j，即
k
i
+
j
≡
0
(
m
o
d
m
)
ki+j \equiv 0 \pmod m
ki+j≡0(modm)；
两边同时乘
i
−
1
×
j
−
1
i^{-1} \times j^{-1}
i−1×j−1 得：
k
j
−
1
+
i
−
1
≡
0
(
m
o
d
m
)
kj^{-1}+i^{-1} \equiv 0 \pmod m
kj−1+i−1≡0(modm)
即
i
−
1
≡
−
k
j
−
1
(
m
o
d
m
)
i^{-1} \equiv -kj^{-1} \pmod m
i−1≡−kj−1(modm)
代入
m
=
k
i
+
j
m= ki + j
m=ki+j 得：
i
−
1
≡
−
⌊
m
i
⌋
(
m
m
o
d
i
)
−
1
(
m
o
d
m
)
i^{-1} \equiv -\lfloor\frac{m}{i}\rfloor (m \bmod i)^{-1} \pmod m
i−1≡−⌊im⌋(mmodi)−1(modm)
故利用迭代易知。
还有一个求
i
!
−
1
i!^{-1}
i!−1 时的小技巧如下：
假设我们要求
i
∈
[
1
,
N
]
i\in[1,N]
i∈[1,N] 时
i
!
i!
i! 在模
m
m
m 意义下的逆元。
不妨先使用费马小定理求出
N
!
−
1
N!^{-1}
N!−1
接着我们发现
i
!
−
1
⋅
i
≡
(
i
−
1
)
−
1
i!^{-1}\cdot i\equiv (i-1)^{-1}
i!−1⋅i≡(i−1)−1
故可以简单地线性递推。
代码
- i − 1 i^{-1} i−1
inv[1]=1;
for (int i=2;i<=n;i++) inv[i]=(long long)(M-M/i)*inv[M%i]%M;
- i ! − 1 i!^{-1} i!−1
fac[0]=1;
for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%M;
inv[n]=pow(fac[n],M-2);
for (int i=K-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%M;
