乘法逆元的求法（5种）

╰半橙微兮° 2021-11-02 09:46 790阅读 0赞

若a\*b≡1（mod p）

即a，b互为mod p意义下的逆元

即（x/a）%p应为x\*b%p

### 一、扩展欧几里得求逆元 ###

根据a\*b+p\*k=1

板子O(logN)：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 typedef long long ll;
     3 ll exgcd(ll a,ll b,ll &x,ll &y) {
     4     if(!b) {
     5         x=1,y=0;
     6         return a;
     7     }
     8     ll res=exgcd(b,a%b,y,x);
     9     y-=a/b*x;       ///x=x1,y=x1-a/b*y1   x1,y1代表下一状态
    10     return res;
    11 }
    12 int main()
    13 {
    14     ll a,p,x,y;  ///扩展欧几里得计算a的逆元（mod p）
    15     scanf("%lld%lld",&a,&p);
    16     ll d=exgcd(a,p,x,y);
    17     printf(d==1?"%lld":"-1",(x+p)%p);///最大公约数不为1，逆元不存在，输出-1
    18     return 0;
    19 }

### 二、费马小定理求逆元(p为素数) ###

p为素数，则有$a^\{p-1\}=1(mod p)$

则$a^\{p-2\}\*a=1(mod p)$

即$a^\{p-2\}$为a mod p意义下的逆元

板子O(logp):

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 typedef long long ll;
     3 ll quickpowmod(ll a,ll b,ll mod) {
     4     ll ans=1;
     5     while(b) {
     6         if(b&1) ans=(ans*a)%mod;
     7         b>>=1;
     8         a=(a*a)%mod;
     9     }
    10     return ans;
    11 }
    12 int main()
    13 {
    14     ll a,p;  ///费马小定理计算a的逆元（mod p）
    15     scanf("%lld%lld",&a,&p);
    16     ll inva=quickpowmod(a,p-2,p);
    17     printf("%lld",inva);
    18     return 0;
    19 }

### 三、欧拉定理求逆元（a，p互素） ###

a,p互素，则有$a^\{\\varphi (p) \}=1(mod p)$

则$a^\{\\varphi (p) -1\}\*a=1(mod p)$

即$a^\{\\varphi (p) -1\}$为a mod p意义下的逆元

板子(logp)：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 typedef long long ll;
     3 ll get_euler(ll x) {
     4     ll ans=x;
     5     for(ll i=2;i*i<=x;i++)
     6         if(x%i==0) {
     7             ans=ans/i*(i-1);
     8             while(ans%i==0) ans/=i;
     9         }
    10     if(ans>1) ans=ans/x*(x-1);
    11     return ans;
    12 }
    13 ll quickpowmod(ll a,ll b,ll mod) {
    14     ll ans=1;
    15     while(b) {
    16         if(b&1) ans=(ans*a)%mod;
    17         b>>=1;
    18         a=a*a%mod;
    19     }
    20     return ans;
    21 }
    22 int main()
    23 {
    24     ll a,p,x,y;
    25     scanf("%lld%lld",&a,&p);    ///a与p互素
    26     ll inva=quickpowmod(a,get_euler(p)-1,p);
    27     printf("%lld",inva);
    28     return 0;
    29 }

### 四、递推求逆元 ###

设p是模数，i是待求的逆元，我们求的是$i^\{-1\}$在mod p意义下的值

$p=k \* i + r $，令 r < i,则k=p/i,r=p%i

$k \* i + r ≡0 (mod p)$

$k \* r^\{-1\} + i^\{-1\} ≡0 (mod p)$

$ i^\{-1\} ≡ - k \* r^\{-1\} (mod p)$

$ i^\{-1\} ≡ - \\frac \{p\} \{i\} \* inv( p mod i ) (mod p) $

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 LL inv[mod+5];
    2 void getInv(LL mod)
    3 {
    4     inv[1]=1;
    5     for(int i=2;i<mod;i++)
    6         inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    7 }

*  适用范围：mod数是不大的素数而且多次调用，比如卢卡斯定理。

### 五、递归求逆元 ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 LL get_inv(int i) {
    2     if(i==1) return 1;
    3     return (mod-mod/i)*(inv[mod%i])%mod;
    4 }

参考博客：[https://blog.csdn.net/xiaoming\_p/article/details/79644386][https_blog.csdn.net_xiaoming_p_article_details_79644386]

转载于:https://www.cnblogs.com/wuliking/p/11247707.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/fa83805a71dd44c7bc4fe2bd2444bb7e.png
[https_blog.csdn.net_xiaoming_p_article_details_79644386]: https://blog.csdn.net/xiaoming_p/article/details/79644386