关于逆元的初学整合

2019-04-14 15:56发布

逆元的几种方法
1. 定义
正整数 a, n,如果有 ax ≡ 1(mod n),则称 x 的最小整数解为 a n
的逆元。
2. 应用
(a / b) mod n = a * b-1 mod n
3. 求解逆元
a) 扩展欧几里得
由逆元定义知 ,求 a 模 n 的逆元 x 即为求解模线性方程
ax ≡ 1(mod n)
适用条件:保证 gcd(a, n) = 1b) 费马小定理
费马小定理:
假如 p 质数,且 gcd(a,p)=1,那么 ap-1 1(mod p)
其中 ap-1 = a * a p-2 , 结合定义可以看出 x = a p-2
适用条件: p 是质数且 gcd(a, p) = 1
c) 线性求逆元
有时题目需要用到 1->p 模 p 的所有质数, p 是奇质数, 用上
面两种方法复杂度差不多都是 O(nlogn), 有一种递推关系可以线性
求出所有逆元。
inv[i] = (p p/i) * inv[p%i] % p , inv[1] = 1;
推导过程:
t = p / i, k = p % i;
t*i+ k 0 (mod p)
=> -t * i k (mod p)
两边同时除以 k*i
=> -t * k-1 i-1 (mod p)
代入 tk, 就有
inv[i] = (p p/i) * inv[p%i] % p
d) 不用逆元。 。。
通常情况下遇到 a/b mod n 的问题时,我们可以通过 a*b-1 mod n
求解, 但是只有当 gcd(b, n) = 1, b 的逆元才存在, 如果出现 gcd !=
1 的情况是如何求解。
有一个通用公式适用所有情况
x = a / b mod n = a mod (n*b) / b
推导过程:
x = (a / b) mod n
= > (a / b) = k * n + x (x < n)
= > a = k * b * n + b * x
= > a mod (b*n) = b * x
= > x = a mod (b*n) / b


乘法逆元的定义貌似是基于群给出的,比较简单地理解,可以说是倒数的概念的推广。记a的关于模p的逆元为a^-1,则a^-1满足aa^-1≡ 1(mod p)
定义:
满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元。

为什么要有乘法逆元呢?
当我们要求(a/b) mod p的值,且a很大,无法直接求得a/b的值时,我们就要用到乘法逆元。
我们可以通过求b关于p的乘法逆元k,将a乘上k再模p,即(a*k) mod p。其结果与(a/b) mod p等价。

证:(其实很简单。。。)
根据b*k≡1 (mod p)有b*k=p*x+1。
k=(p*x+1)/b。
把k代入(a*k) mod p,得:
(a*(p*x+1)/b) mod p
=((a*p*x)/b+a/b) mod p
=[((a*p*x)/b) mod p +(a/b)] mod p
=[(p*(a*x)/b) mod p +(a/b)] mod p
//p*[(a*x)/b] mod p=0
所以原式等于:(a/b) mod p


加减乘与模运算的顺序交换不会影响结果,但是除法不行。有的题目要求结果mod一个大质数,如果原本的结果中有除法,比如除以a,那就可以乘以a的逆元替代。

在mod p的运算中,a存在乘法逆元当且仅当a与p互质。一般题目给的是一个大质数,所以只要a不是p的倍数,就以求乘法逆元。

目前了解到的求法有三种:
1.扩展欧几里得。aa^-1≡ 1(mod p),可以转换为aa^-1 + py = 1,即是扩展欧几里得所能解的ax + by = gcd(a, b)。最常用的解法。 int x, y; int extgcd(int a, int b, int &x, int &y) { if (b == 0){ x = 1; y = 0; return a; } int gcd = exgcd(b, a % b, x, y); int tmp = x; x = y; y = tmp - (a/b) * y; return gcd; } /* 求解ax+by=gcd(a,b),亦即ax≡1(mod b)。函数返回值是a,b的最大公约数,而x即a的逆元。 注意a, b不能写反了。 */
2.由费马小定理a^(p-1)≡ 1(mod p)(p为素数),稍作变形即是 aa^(p-2)≡ 1(mod p),是不是发现了,a^(p-2)即是a的逆元,这个可以用快速幂来求。 3.网上看到的一个很厉害的o(n)的递推,求前n个逆元,不知道是怎么推出来的,但是可以简单地证明一下正确性(要求所mod p为素数)。 首先,1的逆元是1,没什么疑问。
假设前i个数的逆元已经求出,那么
i^-1 = (p%i)^-1 * (p - [p/i]) % p。其中[]表示去尾取整。
(p%i)^-1其实就是(p-[p/i]i)^-1,然后我们左右乘以i,
ii^-1 = (p-[p/i]i)^-1 * ((i-1)p + p-[p/i]i) % p,
其实就是ii^-1 = k^-1 * ((i-1)p + k) % p = 0 + 1 = 1,这样就证完了=。= //字体真糟糕。。 int[] inv = new int[MAXN]; inv[1] = 1; for (int i = 2; i

ACdreamer大神的逆元博客:
今天我们来探讨逆元在ACM-ICPC竞赛中的应用,逆元是一个很重要的概念,必须学会使用它。   对于正整数,如果有,那么把这个同余方程中的最小正整数解叫做的逆元。   逆元一般用扩展欧几里得算法来求得,如果为素数,那么还可以根据费马小定理得到逆元为   推导过程如下                                求现在来看一个逆元最常见问题,求如下表达式的值(已知                 当然这个经典的问题有很多方法,最常见的就是扩展欧几里得,如果是素数,还可以用费马小定理。   但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的,它们都会要求互素。实际上我们还有一 种通用的求逆元方法,适合所有情况。公式如下                现在我们来证明它,已知,证明步骤如下                接下来来实战一下,看几个关于逆元的题目。   题目:http://poj.org/problem?id=1845   题意:给定两个正整数,求的所有因子和对9901取余后的值。   分析:很容易知道,先把分解得到,那么得到,那么      的所有因子和的表达式如下          所以我们有两种做法。第一种做法是二分求等比数列之和。 #include #include #include using namespace std; typedef long long LL; const int N = 10005; const int MOD = 9901; bool prime[N]; int p[N]; int cnt; void isprime() { cnt = 0; memset(prime,true,sizeof(prime)); for(int i=2; i>= 1; a = a * a % MOD; } return ans; } LL sum(LL a,LL n) { if(n == 0) return 1; LL t = sum(a,(n-1)/2); if(n & 1) { LL cur = power(a,(n+1)/2); t = (t + t % MOD * cur % MOD) % MOD; } else { LL cur = power(a,(n+1)/2); t = (t + t % MOD * cur % MOD) % MOD; t = (t + power(a,n)) % MOD; } return t; } void Solve(LL A,LL B) { LL ans = 1; for(int i=0; p[i]*p[i] <= A; i++) { if(A % p[i] == 0) { int num = 0; while(A % p[i] == 0) { num++; A /= p[i]; } ans *= sum(p[i],num*B) % MOD; ans %= MOD; } } if(A > 1) { ans *= sum(A,B) % MOD; ans %= MOD; } cout<>A>>B) Solve(A,B); return 0; }
第二种方法就是用等比数列求和公式,但是要用逆元。用如下公式即可                           因为可能会很大,超过int范围,所以在快速幂时要二分乘法。   #include #include #include using namespace std; typedef long long LL; const int N = 10005; const int MOD = 9901; bool prime[N]; int p[N]; int cnt; void isprime() { cnt = 0; memset(prime,true,sizeof(prime)); for(int i=2; i>= 1; a = (a + a) % m; } return ans; } LL quick_mod(LL a,LL b,LL m) { LL ans = 1; a %= m; while(b) { if(b & 1) { ans = multi(ans,a,m); b--; } b >>= 1; a = multi(a,a,m); } return ans; } void Solve(LL A,LL B) { LL ans = 1; for(int i=0; p[i]*p[i] <= A; i++) { if(A % p[i] == 0) { int num = 0; while(A % p[i] == 0) { num++; A /= p[i]; } LL M = (p[i] - 1) * MOD; ans *= (quick_mod(p[i],num*B+1,M) + M - 1) / (p[i] - 1); ans %= MOD; } } if(A > 1) { LL M = MOD * (A - 1); ans *= (quick_mod(A,B+1,M) + M - 1) / (A - 1); ans %= MOD; } cout<>A>>B) Solve(A,B); return 0; }
其实有些题需要用到的所有逆元,这里为奇质数。那么如果用快速幂求时间复杂度为 如果对于一个1000000级别的素数,这样做的时间复杂度是很高了。实际上有的算法,有一个递推式如下                         它的推导过程如下,设,那么             对上式两边同时除,进一步得到             再把替换掉,最终得到             初始化,这样就可以通过递推法求出模奇素数的所有逆元了。   另外的所有逆元值对应中所有的数,比如,那么对应的逆元是     题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2186   题意:互质的数的个数,其中   分析:因为,所以,我们很容易知道如下结论      对于两个正整数,如果的倍数,那么中与互素的数的个数为        本结论是很好证明的,因为中与互素的个数为,又知道,所以      结论成立。那么对于本题,答案就是                 其中为小于等于的所有素数,先筛选出来即可。由于最终答案对一个质数取模,所以要用逆元,这里       求逆元就有技巧了,用刚刚介绍的递推法预处理,否则会TLE的。   代码: #include #include #include #include using namespace std; typedef long long LL; const int N = 10000005; bitset prime; void isprime() { prime.set(); for(int i=2; i= MOD) break; inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD; } ans2[1] = 1; for(int i=2; i
接下来还有一个关于逆元的有意思的题目,描述如下           证明:                其中        所以只需要证明,而我们知道的逆元对应全部      中的所有数,既是单射也是满射。        所以进一步得到                  证明完毕!