３种方法求乘法逆元

定义

1.离散数学代数系统中的定义：设S为一有二元运算 * 的集合。若e为(S,*)的单位元且a*b=e，则a称为b的左逆元素且b称为a的右逆元素。若一元素x同时是y的左逆元素和右逆元素时，x称为y的两面逆元素或简称为逆元素。S内的一有两面逆元素的元素被称为在S内为可逆的。

2.在乘法中一般有 x*1/x=1 ，当然自然数 0 没有逆元了。

3.数论中的逆元定义 a*b=1(MOD m)

1 拓展欧几里得

描述

求a*b=1(MOD m)
已知gcd(a,b)=1，设a的逆元为x
a*x-1=m*y;
=>a*x+m*y=1;
即转化成求二元一次不定方程的解,x就是a MOD m的逆元

实现

void ex_gcd(long long a,long long b,long long &d,long long &x,long long &y){
    if(b==0){
        d=a;
        x=1;
        y=0;
        return;
    }
    ex_gcd(b,a%b,d,y,x);
    y-=a/b*x;
}
int main(){
    ios::sync_with_stdio(false);
    long long n,m,d,x,y;
    cin>>n>>m;
    ext_gcd(m,n,d,x,y);
    cout<<(x+n)%n<<endl;
    return 0;
}

2 费马小定理及欧拉定理

描述：

1.当P是质数时，且gcd(a,p)=1时有，a^(P-1)=1(MOD P).
2.当P不是质数时，a^phi[P]=1(MOD P).
3.Phi[P]= {P-1 (P是质数)}，
          {phi[a]*b (P=a*b && b is Prime && gcd(a,b)!=1)},
          {phi[a]*(b-1) (P=a*b && b is Prime && gcd(a,b)=1}.

实现

const int maxn=1e7+5;
long long Prime[maxn];
long long phi[maxn];
void Euler(){//先求欧拉函数，这里使用筛法求
    static bool isPrime[maxn];
    memset(isPrime,true,sizeof(isPrime));
    phi[1]=1;
    Prime[0]=0;
    for(int i=2;i<maxn;i++){
        if(isPrime[i]){
            Prime[++Prime[0]]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=Prime[0];j++){
            if(i*Prime[j]>=maxn){
                break;
            }
            isPrime[i*Prime[j]]=false;
            if(i%Prime[j]==0){
                phi[i*Prime[j]]=phi[i]*Prime[j];
                break;
            }else{
                phi[i*Prime[j]]=phi[i]*(Prime[j]-1);
            }
        }
    } 
}
long long fast_mod(long long a,long long n,long long Mod){
    long long ans=1;
    while(n){
        if(n&1){
            ans=(ans*a)%Mod;
        }
        a=(a*a)%Mod;
        n>>=1;
    }
    return ans;
} 
int main (){
    ios::sync_with_stdio(false);
    Euler();
    long long a,m;
    cin>>a>>m;
    cout<<fast_mod(a,phi[m]-1,m)<<endl;
    return 0;
}
/**注意，当P是质数是，只需要fast_mod(a,P-1,P);即可求逆元*/

O（n）打表求逆元；

描述

M=M/i*i+M%i;
=> M/i*i + M%i = 0(MOD M)
=> M%i = -M/i*i（MOD M）
两边同乘M%i的逆元 
=>M%i * inv[M%i] = -M/i * inv[M%i]*i (MOD M)
左边同时加上M*i ，其MOD M为0，不影响等号成立。左边为1。
=>1 = (M-M/i) * inv[M%i]*i(MOD M)
所以，(M-M/i)*inv[M%i] 就是 i 的逆元了。（求i的逆元时，M%i的逆元，一定先求出来了。）

实现

const int maxn=1e6+100;
int inv[maxn];
void Prepare_inv(int n,int M){
    inv[1]=1;
    for(int i=2;i<=n;i++){
        inv[i]=(long long)(M-M/i)*inv[M%i]%M;
    } 
} 

最后

以上就是伶俐小兔子为你收集整理的３种方法求乘法逆元的全部内容，希望文章能够帮你解决３种方法求乘法逆元所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。