本文主要是介绍【数学】乘法逆元进阶，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
乘法逆元基础
可以使用扩展欧几里得算法或费马小定理求得。
乘法逆元进阶
有一种乘法逆元的线性递推算法：
显然 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;
这篇关于【数学】乘法逆元进阶的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
