乘法逆元的具体求法

费马小定理求逆元

  • 费马小定理:a是不能被质数p整除的正整数,则有 a^(p-1) ≡ 1 (mod p)
    求a关于p的乘法逆元,即为a*c≡ 1 (mod p),那么a^(p-2)就是a的逆元
  • Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    LL quickpow(LL x,LL n,LL Mod){
    LL ans=1;
    x%=Mod;
    while(n>0){
    if(n&1) ans=(ans*x)%Mod; //n%2==1
    x=(x*x)%Mod;
    n/=2;
    }
    return ans;
    }
    LL getInv(LL a,LL mod){
    return quickpow(a,mod-2,mod);
    }
    //时间复杂度O(logMod),且当Mod为不能整除a的素数时可用,一般题目给出1e9+7;
    //当Mod-2过大的时候可以使用欧拉降幂防T,a^(Mod-2)%Mod=a^((Mod-2)%phi(Mod)+phi(Mod)) %Mod;

扩欧求逆元

  • 给定模数m,求a的逆相当于求解ax=1(mod m)
    这个方程可以转化为ax-my=1
    然后套用求二元一次方程的方法,用扩展欧几里得算法求得一组x0,y0和gcd
    检查gcd是否为1
    gcd不为1则说明逆元不存在
    若为1,则调整x0到0~m-1的范围中即可
  • Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    LL exgcd(LL a,LL b,LL &x,LL &y)//扩展欧几里得算法 
    {
    if(b==0){
    x=1,y=0;
    return a;
    }
    LL ret=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return ret;
    }
    LL getInv(int a,int mod)//求a在mod下的逆元,不存在逆元返回-1
    {
    LL x,y;
    LL d=exgcd(a,mod,x,y);
    return d==1?(x%mod+mod)%mod:-1;
    }
    //时间复杂度为O(logn),只要存在逆元均可求

线性推逆元

  • 求1,2,…,N关于mod的逆元(mod为质数)
  • Code
    1
    2
    3
    4
    5
    6
    7
    const int mod = 1000000009;
    const int maxn = 10005;
    int inv[maxn];
    inv[1] = 1;
    for(int i = 2; i < 10000; i++)
    inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    //时间复杂度O(N),求1到N所有数的逆元

递归求逆元

  • Code
    1
    2
    3
    4
    5
    6
    LL inv(LL i)
    {
    if(i==1)return 1;
    return (mod-mod/i)*inv(mod%i)%mod;
    }
    //O(logmod),mod是素数
Donate comment here