乘法逆元

定义证明略，介绍三种求解逆元的方法

1.费马小定理

a在模p意义下的逆元为a^(p-2)，此时p为质数。所以我们可以用快速幂进行求解

目测慢哭

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define ll long long
 7 using namespace std;
 8 ll n,p;
 9 int power(ll a,ll b,ll p)
10 {
11     int ret=1;
12     while(b)
13     {
14         if(b%2==1) ret=ret*a%p;
15         a=a*a%p;
16         b>>=1;
17     }
18     return ret;
19 }
20 int main()
21 {
22     scanf("%lld%lld",&n,&p);
23     for(int i=1;i<=n;i++) 
24         printf("%d
",power(i,p-2,p));
25     return 0;
26 }

2.exgcd求逆元

此方法没有对p的限制，而且比前者快很多

exgcd求解的是ax+by=gcd（a,b）的一组可行解

在求逆元时，求的是 ax ≡ 1( mod p )

即求解ax+py=1中的 x ,故使用exgcd

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 ll n,p;
 5 int exgcd(ll a,ll b,ll &x,ll &y)
 6 {
 7     if(b==0) { x=1; y=0;return a; }
 8     int d=exgcd(b,a%b,y,x);
 9     y-=a/b*x;
10     return d;//d=gcd(a,b);
11 }
12 
13 
14 int main()
15 {
16     scanf("%lld%lld",&n,&p);
17     for(int i=1;i<=n;i++)
18     {
19         ll x,y;
20         int d=exgcd(i,p,x,y);
21         x=(x%p+p)%p;
22         printf("%lld
",x);
23     }
24     return 0;
25 }

3.线性求逆元

这个证明不要问我我也不能把你讲懂有个很好的blog

核心语句：

　　　　inv[i] = ( p-p/i ) * inv[p%i] % p ;

 1 #include<iostream>
 2 #include<cstdio>
 3 #define ll long long
 4 #define N 4001000
 5 using namespace std;
 6 int n,p;
 7 int inv[N];
 8 void inverse()
 9 {
10     inv[1]=1; printf("%d
",inv[1]);
11     for(int i=2;i<=n;i++)
12     {
13         if(i>=p) break;
14         inv[i]=(ll)(p-p/i)*inv[p%i]%p;
15         printf("%d
",inv[i]);
16     }
17 }
18 int main()
19 {
20     scanf("%d%d",&n,&p);
21     inverse();
22     return 0;
23 }

然后就没了