浅谈逆元

banned_gutongxing · 2023-07-11 13:33:50 · 个人记录

浅谈逆元

引入

在我们学习 数论 这个板块的时候，有一个并不让人头疼的东西---模运算，当然在这之中普通的运算，可以通过一些性质来算（余数可加性，余数可减性，余数可乘性，余数可乘方性）还是so eazy的。如下 (m>a>b>c>d>0)

a \equiv b (mod\ m),c \equiv d(mod\ m) \Rightarrow (a+c) \equiv ((b+d)\% m)(mod\ m)

a \equiv b (mod\ m),c \equiv d(mod\ m) \Rightarrow (a-c) \equiv ((b-d)\% m)(mod\ m)

a \equiv b (mod\ m),c \equiv d(mod\ m) \Rightarrow (a\times c) \equiv ((b\times d)\% m)(mod\ m)

a \equiv b (mod\ m),c \equiv d(mod\ m) \Rightarrow (a^c) \equiv ((b^d)\% m)(mod\ m)

但是我们并不认同下面这个式子，即余数无可除性。

a \equiv b (mod\ m),c \equiv d(mod\ m) \Rightarrow (a\div c) \equiv ((b\div d)\% m)

因为a与c可能并不整除，所以a\div c有可能并不为整数，而所有的模运算都是建立在整数上的，所以并不行。那么我们又有什么解决方法呢？答案是：有！我们引入一个东西：逆元。

介绍

如果b能满足以下条件: a\times b \equiv 1(mod\ m)，就称做在b是在mod\ m意义下a的逆元，即inv(a) = b。

因为a\times inv(a) \equiv 1(mod\ m)所以我们在mod\ m意义下计算n \div a时，因为a \times inv(a) = 1，所以我们把原式变成n \div a \times \big[a \times inv(a) \big] = n \times inv(a)，所以我们便得到以下式子：

n \div a=n \times inv(a)

求法

既然我们知道了逆元可是怎么求逆元呢？

下面给大家介绍三种常用方法：

费马小定理求逆元

费马小定理：若a与质数p互质，则a^{p-1} \equiv 1 (mod\ p)

由费马小定理得a \cdot a^{p-2} \equiv 1(mod\ p)

也就是说，当模数为质数，且需要求逆元的数与模数互质时，可通过快速幂直接求取其逆元。

参考代码：

int qpow(int a,int n){
    a%=p; //p为模数
    long long res=1; //快速幂答案
    while(n>0){
        if(n&1) res=(res*a)%p;
        a=(a*a)%p;
        n>>=1;
    }
    return res;
}
long long inv(long long a){
    return qpow(a,mod-2);
}

扩张欧几里得算法 b \times inv(b) \equiv 1 (mod\ m)$，看见这个形式，不就是扩欧例题中的不定方程吗。我们再转换一下，为$b \times inv(b) \equiv 1(mod \ m)$，就是 $b \times inv(b) + k \times m=1

当b,m 不互质则无解。

当其互质时，将二者带入扩欧求出解即可。

参考代码：

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int ans=exgcd(b,a%b,x,y);
    int temp=x;
    x=y;
    y=temp-a/b*y;
    return ans;
}
int inv(int a,int p){
    int x,y;
    int g=exgcd(a,p,x,y);
    if(g!=1) return -1;
    else return (x%p+p)%p;
}

线性递归求法如果需要求一个大范围内所有数的逆元，再使用上面的方法会导致TLE，所以我么还需要一种方法来线性求逆元。

设模数为p， p=k \times a+b 。

则，k \times a+b \equiv 0(mod \ p)

同余式两边同乘 inv(a) \times inv(b)，得 k \times inv(b)+inv(a) \equiv 0(mod \ p)。

所以 inv(a)= −k \times inv(b)(mod\ p) 。

因为 k=m \div a,b=m\%a 。

也就是说inv(a)=−(m \div a)×(m\%a)(mod\ m) 。

观察上面的式子可以发现一个数的逆元可以由比它小的数的逆元递推而来。

所以就可以求线性逆元了。

参考代码：

int inv[1000000];
void find_inv(int last,int p){
    inv[1]=1;
    for(int i=2;i<=last;i++) inv[i]=(long long)(p-p/i)*(inv[p%i])%p;
}

完结撒花！