逆元详解

2019-04-13 14:17发布

站内文章 / 模拟电子
15313 0 1591
今天我们来探讨逆元在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
  接下来还有一个关于逆元的有意思的题目，描述如下          证明：由               其中        所以只需要证明，而我们知道模的逆元对应全部      中的所有数，既是单射也是满射。        所以进一步得到                 证明完毕！            

热门文章