【概述】

1.定义：若 ，a、b 互质，则称 x 为 a 的逆元，记为  2.同余模公式 3.应用：当题目要求对结果求 m 的模，且当过程需要计算  时，需要对  取模，即  ，有时 b 过于大，会出现爆精度的情况，所以需要变除法为乘法。 即：设 c 是 b 的逆元 则： 故： 即： 4.求解逆元方法 1）费马小定理 2）扩展欧几里德算法 3）线性求逆元

【费马小定理求逆元】

1.费马小定理

若 a 为一整数，p 是一质数，且  ，那么

2.适用

题目要求模 p 为素数的情况。

3.方法

由  可得 ，即得  是 a 的逆元。

4.实现

#define MOD 1000000007 long long quick_pow(long long a,long long b) { int res=1,base=a%MOD; while(b) { if(b&1) res=(base*res)%MOD; base=(base*base)%MOD; b>>=1; } return res; } long long inv(long long a) { return quick_pow(a,MOD-2); }

【扩展欧几里德算法求逆元】

1.适用

题目要求模 m 为素数的情况。

2.方法

由逆元定义可知 ，求 a 模 m 的逆元 x ，即为求解同余方程 将方程转化为 ，然后套用解同余方程的方法，用扩展欧几里得算法求得一组  和 然后检查  是否为 1 ，若不为 1 说明逆元不存在，若为 1 ，则调整  到  的范围中即可。

3.实现

long long Extended_GCD(long long a,long long b,long long &x,long long &y) { if(b==0) { x=1; y=0; return a; } long long gcd=Extended_GCD(b,a%b,y,x); y=y-(a/b)*x; return gcd; } long long inv(long long a) { long long x,y; Extended_GCD(a,MOD,x,y); x=(x%MOD+MOD)%MOD return x }

【线性求逆元】

1.适用

在模质数 p 下，求 1~n 所有逆元，用上面两种方法复杂度差不多都是 O(nlogn)，通过递推关系可以线性求出所有逆元。

2.方法

已知，1的逆元一定是1，故有： ① 设  ② 将 ② 代入 ① 有： 即： 两边同除 ，得： 代入 t、 k， 有： 综上，易得：

3.实现

int inv[N]; long long Inv(int n) { inv[1]=1; for(int i=2;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p; }

【说明】

通常情况下，遇到  的问题时，一般通过费马小定理来解决，但是只有当  时，b 的逆元才存在。 对于   的情况，有一通用公式： 其推导如下 对于公式： ，其适用于所有的情况，无需区分互不互素，而费马小定理和扩展欧几里德算法求逆元具有局限性的，它们都会要求 b 与 k 互素，如果两者不互质，那就没有逆元。 当两者互质的时候，b 与 k 可能会很大，不适合套用一般公式，因此大部分时还是使用逆元处理。