乘法逆元（P3811）(四种方法)

适合单个的，费马小定理，exgcd，都是不错的选择，利用积性函数的方法和欧拉筛的方法适合批量求，但是论时间和空间的话，还是积性函数的方法比较好用，线性的。

题目链接：https://www.luogu.org/problemnew/show/P3811

方法一（超时）（适合求单个）：费马小定理
当p为素数的时候，a^(p-1)=1(在模p的情况下),所以我们就可以推导出，a*a^(p-2)=1,所以a的逆元就是a^(p-2)。

代码：

 1 #include<iostream>
 2 #include<stack>
 3 #include<cmath>
 4 #include<queue>
 5 #include<stdio.h>
 6 #include<algorithm>
 7 using namespace std;
 8 # define ll long long
 9 # define inf 0x3f3f3f3f
10 const int maxn = 1e5+100;
11 ll quickpow(ll t1,ll t2,ll t){
12 ll ans=t1%t;
13 t2--;
14 while(t2){
15 if(t2&1)ans=ans*t1%t;
16 t1=t1*t1%t;
17 t2>>=1;
18 }
19 return ans%t;
20 }
21 ll inv(ll t,ll mod){
22 return quickpow(t,mod-2,mod)%mod;
23 }
24 int main(){
25 ll n,p;
26 scanf("%lld %lld",&n,&p);
27 for(int i=1;i<=n;i++){
28 printf("%lld
",inv(i,p));
29 }
30 return 0;
31 }

View Code

方法二（超时）（适合求单个）：扩展欧几里得

a*x=1（mod p),我们可以列出等式，a*x+p*y=1,利用扩展欧几里得，直接求出x。

代码：

 1 #include<iostream>
 2 #include<stack>
 3 #include<cmath>
 4 #include<queue>
 5 #include<stdio.h>
 6 #include<algorithm>
 7 using namespace std;
 8 # define ll long long
 9 # define inf 0x3f3f3f3f
10 const int maxn = 1e5+100;
11 ll x,y;
12 void exgcd(ll t1,ll t2,ll mod)
13 {
14     if(t2==0)
15     {
16         x=1;
17         y=0;
18         return ;
19     }
20     exgcd(t2,t1%t2,mod);
21     ll tmp=x%mod;
22     x=y%mod;
23     y=(tmp-t1/t2*y%mod+mod)%mod;
24 }
25 ll inv(ll t,ll mod)
26 {
27     exgcd(t,mod,mod);
28     return x%mod;
29 }
30 int main()
31 {
32     ll n,p;
33     scanf("%lld %lld",&n,&p);
34     for(int i=1; i<=n; i++)
35     {
36         printf("%lld
",inv(i,p));
37     }
38     return 0;
39 }

View Code

方法三（AC）（可批量求）：积性函数

证明方法如下图所示：

AC代码：

 1 #include<iostream>
 2 #include<stack>
 3 #include<cmath>
 4 #include<queue>
 5 #include<stdio.h>
 6 #include<algorithm>
 7 using namespace std;
 8 # define ll long long
 9 # define inf 0x3f3f3f3f
10 const int maxn = 2e7+1000;
11 ll inv[maxn];
12 int main()
13 {
14     ll n,p;
15     scanf("%lld %lld",&n,&p);
16     inv[1]=1;
17     for(int i=2;i<=n;i++){
18     inv[i]=((p-p/i)*inv[p%i]+p)%p;
19     }
20     for(int i=1;i<=n;i++){
21     printf("%lld
",inv[i]);
22     }
23     return 0;
24 }

View Code

方法四：

欧拉筛（可批量求）

AC代码：

 1 #include<iostream>
 2 #include<stack>
 3 #include<cmath>
 4 #include<queue>
 5 #include<stdio.h>
 6 #include<algorithm>
 7 using namespace std;
 8 # define ll long long
 9 # define inf 0x3f3f3f3f
10 const int maxn = 2e7+1000;
11 ll inv[maxn],prim[maxn],vis[maxn];
12 ll quickpow(ll  t1,ll t2,ll mod)
13 {
14 if(!t2)return 1;
15 ll now=quickpow(t1,t2>>1,mod);
16 now=now*now%mod;
17 if(t2&1)now=now*t1%mod;
18 return now%mod;
19 }
20 int main()
21 {
22     ll n,p;
23     scanf("%lld %lld",&n,&p);
24     vis[1]=1;
25     inv[1]=1;
26     int num=0;
27     for(ll i=2; i<=n; i++)
28     {
29         if(vis[i]==0)
30         {
31             prim[++num]=i;
32             inv[i]=quickpow(i,p-2,p);
33         }
34         for(ll j=1; j<=num; j++)
35         {
36             if(i*prim[j]>n)
37                 break;
38             ll tmp=i*prim[j];
39            vis[tmp]=1;
40             inv[i*prim[j]%p]=inv[i]*inv[prim[j]]%p;
41             if(i%prim[j]==0)
42                 break;
43         }
44     }
45     for(int i=1; i<=n; i++)
46     {
47         printf("%lld
",inv[i]);
48     }
49     return 0;
50 }

View Code