【数论】乘法逆元总结

2019-04-14 18:27发布

站内文章 / 模拟电子
13384 0 1559

前言：

我们知道在模意义下的加减乘运算都是具有封闭性的，但除法确是例外，所以我们就要找一种在模意义下代替除法运算的东西
想看代码的在最下方

定义：

如果有ab≡1(modp)，则称b是mod p意义下a的乘法逆元。记b=inv（a）或b=a−1(定义了剩余系中的除法)

性质：

一个数有逆元的充分必要条件是gcd(a,n)=1，此时逆元唯一存在
(ab)modp=((amodp)×(bmodp)modp

求法：

1.扩展欧几里得
ax≡1(modp)可以等价的转化为ax−py=1
然后套用exgcd解方程，并检查gcd（a，p）是否等于1
如果gcd（a，p）=1，把x调整到1~p−1即可
复杂度O(log n) 2.费马小定理
费马小定理的具体内容和证明请点击这里
由ap−1≡1(mod p)得a×ap−2≡1(mod p)
所以当模数是一个质数的时候，可以用费马小定理求解，即inv(i)=ip−2(mod p),复杂度O(log n),
3.欧拉定理
由aφ（p）≡1(mod p)得aφ（p）−1是a的逆元
适用于模数不是素数
4.递推
O（n）的时间可以处理出1~n在modp 意义下的逆元，方法如下
这里写图片描述
那么我们就可以做到线性递推 inv[i]=(mod-mod/i)*inv[mod%i]%mod; ps：
1.求(ab)modp时，如果b×p的计算不会爆掉的话，可以转化成
a%(b×p)bmodp省略求逆元的步骤，还是很方便的
2.在计算组合数时需要用到阶乘的逆元，也可以做到O(n)递推，方法如下 fac[0] = 1; for(int i = 1; i <= MAX; i++) fac[i] = (fac[i - 1] * i) % MOD; inv_fac[MAX] = qpow(fac[MAX], MOD - 2); for(int i = MAX - 1; i >= 0; i--) inv_fac[i] = (inv_fac[i + 1] * (i + 1)) % MOD; 下为几种方法求逆元的代码实现 #include #include #include #include using namespace std; #define LL long long int inv[1000010]; LL ksm(LL a,LL b,LL mod) { int ans=1; while(b) { if(b&1) ans=(ans*a)%mod; a=(a*a)%mod; b>>=1; } return ans; } LL exgcd(LL a,LL b,LL &x,LL &y) { if(!b) { x=1; y=0; return a; } LL GCD=exgcd(b,a%b,x,y); LL tmp=x; x=y; y=tmp-a/b*y; return GCD; } LL inv1(LL a,LL mod)//扩展欧几里得求逆元 { LL x,y; LL d=exgcd(a,mod,x,y); if(d==1) return (x%mod+mod)%mod; return -1; } LL inv2(LL a,LL mod)//费马小定理 { return ksm(a,mod-2,mod); } void inv3(LL mod)//线性递推求逆元 { inv[1]=1; for(int i=2;i<=mod-1;i++) { inv[i]=(mod-mod/i)*inv[mod%i]%mod; cout<" "; } } int main() { LL n,mod; while(cin>>n>>mod) { cout<mod)<<" "<mod)<mod); } }

热门文章