如何详细解释并理解数学中的逆元概念及其应用？

本文共计2762个文字，预计阅读时间需要12分钟。

今天我们来探讨逆元在ACM-ICPC竞赛中的应用。逆元是一个非常重要的概念，必须学会使用。

对于整数a和模m，如果存在整数b，使得a*b ≡ 1 (mod m)，那么b就是a在模m下的逆元。

例如，对于整数5和模11，我们可以找到其逆元是9，因为5*9 ≡ 1 (mod 11)。

在算法中，逆元常用于解决诸如求逆元、模逆、求逆序元等问题。

今天我们来探讨逆元在ACM-ICPC竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。

对于正整数

和

，如果有

，那么把这个同余方程中

的最小正整数解叫做

模

的逆元。

逆元一般用扩展欧几里得算法来求得，如果

为素数，那么还可以根据费马小定理得到逆元为

。

推导过程如下

求现在来看一个逆元最常见问题，求如下表达式的值（已知

）

当然这个经典的问题有很多方法，最常见的就是扩展欧几里得，如果

是素数，还可以用费马小定理。

但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求

与

互素。实际上我们还有一

种通用的求逆元方法，适合所有情况。公式如下

现在我们来证明它，已知

，证明步骤如下

接下来来实战一下，看几个关于逆元的题目。

题目：​​poj.org/problem?id=1845​​

​

题意：给定两个正整数

和

，求

的所有因子和对9901取余后的值。

分析：很容易知道，先把

分解得到

，那么得到

，那么

的所有因子和的表达式如下

所以我们有两种做法。第一种做法是二分求等比数列之和。

代码：

[cpp] ​​view plain​​ ​​copy​​

​​​ ​​​

1. #include<iostream>
2. #include<string.h>
3. #include<stdio.h>
5. usingnamespacestd;
6. typedeflonglongLL;
7. constintN=10005;
8. constintMOD=9901;
10. boolprime[N];
11. intp[N];
12. intcnt;
14. voidisprime()
15. {
16. cnt=0;
17. true,sizeof(prime));
18. for(inti=2;i<N;i++)
19. {
20. if(prime[i])
21. {
22. p[cnt++]=i;
23. for(intj=i+i;j<N;j+=i)
24. false;
25. }
26. }
27. }
29. LLpower(LLa,LLb)
30. {
31. LLans=1;
32. a%=MOD;
33. while(b)
34. {
35. if(b&1)
36. {
37. ans=ans*a%MOD;
38. b--;
39. }
40. b>>=1;
41. a=a*a%MOD;
42. }
43. returnans;
44. }
46. LLsum(LLa,LLn)
47. {
48. if(n==0)return1;
49. LLt=sum(a,(n-1)/2);
50. if(n&1)
51. {
52. LLcur=power(a,(n+1)/2);
53. t=(t+t%MOD*cur%MOD)%MOD;
54. }
55. else
56. {
57. LLcur=power(a,(n+1)/2);
58. t=(t+t%MOD*cur%MOD)%MOD;
59. t=(t+power(a,n))%MOD;
60. }
61. returnt;
62. }
64. voidSolve(LLA,LLB)
65. {
66. LLans=1;
67. for(inti=0;p[i]*p[i]<=A;i++)
68. {
69. if(A%p[i]==0)
70. {
71. intnum=0;
72. while(A%p[i]==0)
73. {
74. num++;
75. A/=p[i];
76. }
77. ans*=sum(p[i],num*B)%MOD;
78. ans%=MOD;
79. }
80. }
81. if(A>1)
82. {
83. ans*=sum(A,B)%MOD;
84. ans%=MOD;
85. }
86. cout<<ans<<endl;
87. }
89. intmain()
90. {
91. LLA,B;
92. isprime();
93. while(cin>>A>>B)
94. Solve(A,B);
95. return0;
96. }

第二种方法就是用等比数列求和公式，但是要用逆元。用如下公式即可

因为

可能会很大，超过int范围，所以在快速幂时要二分乘法。

代码：

[cpp] ​​view plain​​ ​​copy​​

​​​ ​​​

1. #include<iostream>
2. #include<string.h>
3. #include<stdio.h>
5. usingnamespacestd;
6. typedeflonglongLL;
7. constintN=10005;
8. constintMOD=9901;
10. boolprime[N];
11. intp[N];
12. intcnt;
14. voidisprime()
15. {
16. cnt=0;
17. true,sizeof(prime));
18. for(inti=2;i<N;i++)
19. {
20. if(prime[i])
21. {
22. p[cnt++]=i;
23. for(intj=i+i;j<N;j+=i)
24. false;
25. }
26. }
27. }
29. LLmulti(LLa,LLb,LLm)
30. {
31. LLans=0;
32. a%=m;
33. while(b)
34. {
35. if(b&1)
36. {
37. ans=(ans+a)%m;
38. b--;
39. }
40. b>>=1;
41. a=(a+a)%m;
42. }
43. returnans;
44. }
46. LLquick_mod(LLa,LLb,LLm)
47. {
48. LLans=1;
49. a%=m;
50. while(b)
51. {
52. if(b&1)
53. {
54. ans=multi(ans,a,m);
55. b--;
56. }
57. b>>=1;
58. a=multi(a,a,m);
59. }
60. returnans;
61. }
63. voidSolve(LLA,LLB)
64. {
65. LLans=1;
66. for(inti=0;p[i]*p[i]<=A;i++)
67. {
68. if(A%p[i]==0)
69. {
70. intnum=0;
71. while(A%p[i]==0)
72. {
73. num++;
74. A/=p[i];
75. }
76. LLM=(p[i]-1)*MOD;
77. ans*=(quick_mod(p[i],num*B+1,M)+M-1)/(p[i]-1);
78. ans%=MOD;
79. }
80. }
81. if(A>1)
82. {
83. LLM=MOD*(A-1);
84. ans*=(quick_mod(A,B+1,M)+M-1)/(A-1);
85. ans%=MOD;
86. }
87. cout<<ans<<endl;
88. }
90. intmain()
91. {
92. LLA,B;
93. isprime();
94. while(cin>>A>>B)
95. Solve(A,B);
96. return0;
97. }

其实有些题需要用到

模

的所有逆元，这里

为奇质数。那么如果用快速幂求时间复杂度为

，如果对于一个1000000级别的素数

，这样做的时间复杂度是很高了。实际上有

的算法，有一个递推式如下

它的推导过程如下，设

，那么

对上式两边同时除

，进一步得到

再把

和

替换掉，最终得到

初始化

，这样就可以通过递推法求出

模奇素数

的所有逆元了。

另外

模

的所有逆元值对应

中所有的数，比如

，那么

对应的逆元是

。

题目：​​www.lydsy.com/JudgeOnline/problem.php?id=2186​​

​

题意：求

中

互质的数的个数，其中

。

分析：因为

，所以

，我们很容易知道如下结论

对于两个正整数

和

，如果

是

的倍数，那么

中与

互素的数的个数为

​

本结论是很好证明的，因为

中与

互素的个数为

，又知道

，所以

结论成立。那么对于本题，答案就是

其中

为小于等于

的所有素数，先筛选出来即可。由于最终答案对一个质数取模，所以要用逆元，这里

求逆元就有技巧了，用刚刚介绍的递推法预处理，否则会TLE的。

代码：

[cpp] ​​view plain​​ ​​copy​​

​​​ ​​​

1. #include<iostream>
2. #include<string.h>
3. #include<stdio.h>
4. #include<bitset>
6. usingnamespacestd;
7. typedeflonglongLL;
8. constintN=10000005;
10. bitset<N>prime;
12. voidisprime()
13. {
14. prime.set();
15. for(inti=2;i<N;i++)
16. {
17. if(prime[i])
18. {
19. for(intj=i+i;j<N;j+=i)
20. false;
21. }
22. }
23. }
25. LLans1[N],ans2[N];
26. LLinv[N];
28. intmain()
29. {
30. isprime();
31. intMOD,m,n,T;
32. "%d%d",&T,&MOD);
33. ans1[0]=1;
34. for(inti=1;i<N;i++)
35. ans1[i]=ans1[i-1]*i%MOD;
36. inv[1]=1;
37. for(inti=2;i<N;i++)
38. {
39. if(i>=MOD)break;
40. inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
41. }
42. ans2[1]=1;
43. for(inti=2;i<N;i++)
44. {
45. if(prime[i])
46. {
47. ans2[i]=ans2[i-1]*(i-1)%MOD;
48. ans2[i]=ans2[i]*inv[i%MOD]%MOD;
49. }
50. else
51. {
52. ans2[i]=ans2[i-1];
53. }
54. }
55. while(T--)
56. {
57. "%d%d",&n,&m);
58. LLans=ans1[n]*ans2[m]%MOD;
59. "%lld\n",ans);
60. }
61. return0;
62. }

接下来还有一个关于逆元的有意思的题目，描述如下

证明：由

其中

所以只需要证明

，而我们知道

模

的逆元对应全部

中的所有数，既是单射也是满射。

所以进一步得到

证明完毕！