首先说明逆元的概念,类似于倒数的性质。

方程ax≡1(mod p),的解称为a关于模p的逆,当gcd(a,p)==1(即a,p互质)时,方程有唯一解,否则无解。

对于一些题目会要求把结果MOD一个数,通常是一个较大的质数,对于加减乘法通过同余定理可以直接拆开计算,

但对于(a/b)%MOD这个式子,是不可以写成(a%MOD/b%MOD)%MOD的,但是可以写为(a*b^-1)%MOD,其中b^-1表示b的逆元。

1.扩展欧几里得

给定模数m,求a的逆相当于求解ax=1(mod m)这个方程可以转化为ax-my=1

然后套用求二元一次方程的方法,用扩展欧几里得算法求得一组x0,y0和gcd

检查gcd是否为1

gcd不为1则说明逆元不存在

若为1,则调整x0到0~m-1的范围中即可

PS:这种算法效率较高,常数较小,时间复杂度为O(log n)

#include<bits/stdc++.h>
using namespace std;

int exgcd(int a,int b,int d,int &x,int &y){
    if (b==0){
        d=a;
        x=1,y=0;
        return a;
    }
    int q=exgcd(b,a%b,d,y,x);
    y-=a/b*x;
    return q;
} 
int inverse(int a,int n){
    int d,x,y;
    exgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}
int main(){
    int a,b;
    cin>>a>>b;
    cout<<inverse(a,b);
    system("pause");
    return 0;
}

2.费马小定理

在模为素数p的情况下,有费马小定理

a^(p-1)=1(mod p)

那么a^(p-2)=a^-1(mod p)

也就是说a的逆元为a^(p-2)

而在模不为素数p的情况下,有欧拉定理

a^phi(m)=1(mod m) (a⊥m)

同理a^-1=a^(phi(m)-1)

因此逆元x便可以套用快速幂求得了x=a^(phi(m)-1)

但是似乎还有个问题?如何判断a是否有逆元呢?

检验逆元的性质,看求出的幂值x与a相乘是否为1即可

PS:这种算法复杂度为O(logN)在几次测试中,常数似乎较上种方法大

当p比较大的时候需要用快速幂求

当模p不是素数的时候需要用到欧拉定理

a^phi(p)≡1               (mod p)

a*a^(phi(p)-1)≡1      (mod p)

a^(-1)≡a^(phi(p)-1)  (mod p)

所以

时间复杂度即求出单个欧拉函数的值

(当p为素数的时候phi(p)=p-1,则phi(p)-1=p-2可以看出欧拉定理是费马小定理的推广)

void inverse(int n, int p) {
    inv[1] = 1;
    for (int i=2; i<=n; ++i) {
        inv[i] = (p - p / i) * inv[p%i] % p;
    }

2 Replies to “逆元的求法”

  1. Google Chrome 63.0.3239.132 Google Chrome 63.0.3239.132 Windows 10 x64 Edition Windows 10 x64 Edition
    Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/63.0.3239.132 Safari/537.36

    牛逼

发表评论

电子邮件地址不会被公开。 必填项已用*标注