请耐心等待,依据费马小定理

 

逆元的三种解法(附详细表明),二种解法评释

 

友谊提示:

Latex加载稍慢,请耐心等待

友谊提醒:

如何是逆元?

若$x$满足

$a*x\equiv 1(\mod p)$

我们称$x$是$a$在$\mod p$意义下的逆元

 

Latex加载稍慢,请耐心等待

逆元的为主解法

https://loj.ac/problem/110

怎么是逆元?

若$x$满足

$a*x\equiv 1(\mod p)$

我们称$x$是$a$在$\mod
p$意义下的逆元

 

1.快速幂

当p为素数

依照费马小定理

$a^{(p-1)}\equiv 1(mod p)$

${\color{Green}a*a^{(p-2)}\equiv 1(mod p) }$

 

引导急速幂就好啊

日子复杂度:$O(log_2^p)$

 1 #include<cstdio>
 2 #define LL long long 
 3 using namespace std;
 4 const LL MAXN=200000001;
 5 LL n,mod;
 6 LL fastpow(LL val,LL p)
 7 {
 8     LL base=1;
 9     while(p)
10     {
11         if(p&1)    base=(base*val)%mod;
12         val=(val*val)%mod;
13         p>>=1;
14     }
15     return base;
16 }
17 int main()
18 {
19     scanf("%lld%lld",&n,&mod);
20     for(LL i=1;i<=n;i++)
21         printf("%lld\n",fastpow(i,mod-2)%mod);
22     return 0;
23 }

逆元的主导解法

https://loj.ac/problem/110

2.扩展欧几里得

对于$a*x\equiv 1(mod p)$

他的另一种写法为

$a*x+b*y=1$(想一想,为什么)

扩展欧几里得,带入求解

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int n,mod;
 6 inline int read()
 7 {
 8     char c=getchar();int  flag=1,x=0;
 9     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
10     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();    return x*flag;
11 }
12 int x,y;
13 int gcd(int a,int b)
14 {
15     return b==0?a:gcd(b,a%b);
16 }
17 int exgcd(int a,int b,int &x,int &y)
18 {
19     if(b==0)
20     {
21         x=1,y=0;
22         return a;
23     }
24     int r=exgcd(b,a%b,x,y);
25     int tmp=x;x=y;y=tmp-(a/b)*y;
26     return r;
27 }
28 int main()
29 {
30     n=read(),mod=read();
31     for(int i=1;i<=n;i++)
32     {
33         int g=exgcd(i,mod,x,y);
34         while(x<0)    x+=mod;
35         printf("%d\n",x);
36     }
37     return 0;
38 }

岁月复杂度:$O(log_2^n)$

 

1.快速幂

当p为素数

好玩的事费马小定理

$a^{(p-1)}\equiv 1(mod p)$

${\color{Green}a*a^{(p-2)}\equiv 1(mod
p) }$

 

带走快捷幂就好啊

岁月复杂度:$O(log_2^p)$

 1 #include<cstdio>
 2 #define LL long long 
 3 using namespace std;
 4 const LL MAXN=200000001;
 5 LL n,mod;
 6 LL fastpow(LL val,LL p)
 7 {
 8     LL base=1;
 9     while(p)
10     {
11         if(p&1)    base=(base*val)%mod;
12         val=(val*val)%mod;
13         p>>=1;
14     }
15     return base;
16 }
17 int main()
18 {
19     scanf("%lld%lld",&n,&mod);
20     for(LL i=1;i<=n;i++)
21         printf("%lld\n",fastpow(i,mod-2)%mod);
22     return 0;
23 }

 3.递推

前三种办法常用来求单个逆元

对此逆元的要求量十分大的时候,大家能够运用递推的主意来求逆元

前提条件:$P$为素数

推倒进度

设$t=P/i$
$k=P \mod i$

显然有

$t*i+k \equiv  0 (\mod P)$

$k \equiv -t*i(\mod P)$

两边同除$i*k$,把$t$和$k$带入

$inv[i] \equiv -p/i*inv[p \mod i] (\mod p)$

那边须求注意一个职业,

对于 $a\mod p$当$a<0$时,

应为$(a+p) \mod p$

把原式的$\mod p$消掉,得

$inv[i]=P-P/i*inv[P\mod i]$

如此那般就足以进行线性的递推啦

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define LL unsigned long long 
 6 using namespace std;
 7 const LL MAXN=200000001;
 8 inline LL read()
 9 {
10     char c=getchar();LL flag=1,x=0;
11     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
12     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();    return x*flag;
13 }
14 LL inv[MAXN];
15 LL n,p;
16 int main()
17 {
18     n=read(),p=read();
19     inv[1]=1;
20     printf("1\n");
21     for(int i=2;i<=n;i++)
22     {
23         inv[i]=(p-p/i)*inv[p%i]%p;
24         printf("%d\n",inv[i]);
25     }
26     return 0;
27 }

 

时间复杂度:$O(n)$

2.恢宏欧几里得

对于$a*x\equiv 1(mod p)$

他的另一种写法为

$a*x+p*y=1$(想一想,为什么)

强大欧几里得,带入求解

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int n,mod;
 6 inline int read()
 7 {
 8     char c=getchar();int  flag=1,x=0;
 9     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
10     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();    return x*flag;
11 }
12 int x,y;
13 int gcd(int a,int b)
14 {
15     return b==0?a:gcd(b,a%b);
16 }
17 int exgcd(int a,int b,int &x,int &y)
18 {
19     if(b==0)
20     {
21         x=1,y=0;
22         return a;
23     }
24     int r=exgcd(b,a%b,x,y);
25     int tmp=x;x=y;y=tmp-(a/b)*y;
26     return r;
27 }
28 int main()
29 {
30     n=read(),mod=read();
31     for(int i=1;i<=n;i++)
32     {
33         int g=exgcd(i,mod,x,y);
34         while(x<0)    x+=mod;
35         printf("%d\n",x);
36     }
37     return 0;
38 }

时刻复杂度:$O(log_2^n)$

 

总结

在求多个数的逆元的时候,推荐使用递推算法

在求单个数的逆元的时候,推荐应用扩张欧几里得算法

因为扩张欧几里得算法不受模数的界定,而且自测运营效用比快捷幂高非常多

 

http://www.bkjia.com/cjjc/1230452.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1230452.htmlTechArticle逆元的三种解法(附详细证明),三种解法证明
友情提醒: Latex加载稍慢,请耐心等待 什么是逆元? 若$x$满意 $a*x\equiv
1(\mod p)$ 我们称$x$是…

 3.递推

前三种办法常用来求单个逆元

对此逆元的需求量十分大的时候,大家能够运用递推的方式来求逆元

前提条件:$P$为素数

演绎进度

设$t=P/i$
$k=P \mod i$

显然有

$t*i+k \equiv  0 (\mod P)$

$k \equiv -t*i(\mod P)$

两边同除$i*k$,把$t$和$k$带入

$inv[i] \equiv -p/i*inv[p \mod i]
(\mod p)$

那边要求注意叁个事情,

对于 $a\mod p$当$a<0$时,

应为$(a+p) \mod p$

那样就可以把原式的$\mod
p$消掉,得

$inv[i]=P-P/i*inv[P\mod i]$

如此就能够进行线性的递推啦

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define LL unsigned long long 
 6 using namespace std;
 7 const LL MAXN=200000001;
 8 inline LL read()
 9 {
10     char c=getchar();LL flag=1,x=0;
11     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
12     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();    return x*flag;
13 }
14 LL inv[MAXN];
15 LL n,p;
16 int main()
17 {
18     n=read(),p=read();
19     inv[1]=1;
20     printf("1\n");
21     for(int i=2;i<=n;i++)
22     {
23         inv[i]=(p-p/i)*inv[p%i]%p;
24         printf("%d\n",inv[i]);
25     }
26     return 0;
27 }

 

时光复杂度:$O(n)$

总结

在求多少个数的逆元的时候,推荐应用递推算法

在求单个数的逆元的时候,推荐使用扩大欧几里得算法

因为扩充欧几里得算法不受模数的限定,並且自测运营功用比神速幂高相当多

 

相关文章