2025年逆元inv详细整理

科技前沿 • 2025-03-15 09:05 • 阅读 41

大家好，我是讯享网，很高兴认识大家。

个人笔记，仅供复习

1.概念

1.1 定义：逆元素是指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和乘法中的倒数。

1.2 数论中定义：如果满足公式，a*b = 1（mod P），则a是b的逆元，同时b也是a的逆元。

1.3 另一种定义：a*x = 1 (mod P)，其中a与P互质，则称x的最小整数为a关于P的逆元。

2.逆元的应用

2.1 除法模运算：设c为b在对P取模状态下的逆元，在求(a/b)%P时，很可能会因为b过大而超过精度范围，这时候可以将除法转换成乘法来做，（a/b）%P = (a*Invb)%P = (a%P)*(Invb%P)%P。

3.求逆元的常用方法

3.1 费马小定理

费马小定理：若p为素数，则有 $a^{p-1}\equiv1(mod P)$
讯享网

推论： $a*a^{p-2}\equiv 1(mod P)$

故 $a^{p-2}$ 就是a关于P的一个逆元

3.1.1代码实例：

#include<iostream> #include<cstdio> using namespace std; const int maxn = ; const int Mod = 1e5+7; typedef long long LL; LL Finv[maxn]; LL Qpow(LL x,LL p,LL m){//快速幂算法 LL res = 1; while(p){ if(p&1) res =res*x%m; x = x*x%m; p >>= 1; } return res; } void Init(){//用来求逆元 Finv[1] = 1; for(int i = 2;i < maxn;i++) Finv[i] = Qpow(i,Mod-2,Mod); } int main() { Init(); for(int i = 1;i < maxn;i++) cout << Finv[i] << " "; return 0; }

讯享网

3.1.2 复杂度分析：求单个逆元的时间复杂度是lg(Mod)

3.2 拓展欧几里得算法

求a关于1模P的逆元 $a\equiv 1(mod P)$ ，可以转化为a*X = 1+K*P，其中X与P都是整数，这样X即为所求逆元。

这样就可以转化为拓展欧几里得算法（要求a与P互质）：a*X + K*P = 1；

3.3 逆元线性筛

递推式：inv[i] = (Mod-Mod / i) * inv[Mod% i]%Mod

推导：假设t = Mod / i（向下取整），k = Mod % i，那么t * i + k = Mod；

因为 $t*i+k \equiv 0(mod Mod)$ ；

等式两边同时除 i * k，得：

$t*k^{-1} + i^{-1} \equiv 0(mod Mod)$ ；

移项，得：

$i^{-1} \equiv t*k^{-1} (mod Mod)$ ;

即 inv[i] = (-Mod/i)*inv[Mod% i]%Mod

如果要保证结果为正： inv[i] = (Mod-Mod / i) * inv[Mod% i]%Mod

3.3.1 代码实例：

讯享网#include<iostream> #include<cstdio> using namespace std; typedef long long LL; const int maxn = ; const int Mod = 1e5+7; LL inv[maxn]; void Inv(){ inv[0] = inv[1] = 1; for(LL i = 2;i < maxn;i++){ inv[i] = (Mod - Mod/i)*inv[Mod%i]%Mod; } } int main() { Inv(); return 0; }

3.3.2 算法复杂度分析：线性时间递推，时间复杂度O(lg n)

3.3.3 求 n! 逆元：

inv[i] = inv[i+1] * (i + 1) % Mod

#include<iostream> #include<cstdio> using namespace std; const int maxn = ; const int Mod = 1e9+7; typedef long long LL; LL Finv[maxn],F[maxn];//F存阶乘，Finv存对应逆元 LL Qpow(LL x,LL p,LL m){ LL res = 1; while(p){ if(p&1) res =res*x%m; x = x*x%m; p >>= 1; } return res; } void Init(){ F[0] = 1; for(LL i = 1;i < maxn;i++) F[i] = F[i-1]*i%Mod; Finv[maxn-1] = Qpow(F[maxn-1],Mod-2,Mod); for(int i = maxn-1;i > 0;i--) Finv[i-1] = Finv[i]*i%Mod; } int main() { Init(); for(int i = 1;i < maxn;i++) cout << Finv[i]*F[i]%Mod << "\t"; return 0; }