逆元

约 375 个字 81 行代码预计阅读时间 2 分钟

定义¶

模 $n$ 意义下，一个数 $a$ 可能有唯一的与之对应的乘法逆元 $x$ ，使得 $a*x \equiv 1\pmod n$

存在逆元的充分必要条件¶

$gcd(a,n)=1$ ，此时逆元唯一存在

用处¶

模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x

即： $(a/b)\%p=(a\%p*inv(b)\%p)\%p$

求逆元方法¶

exgcd¶

时间复杂度¶

$O(log_e n)$

原理¶

求a的逆元相当于求解ax=1(mod n),

这个方程可以转化为ax-ny=1

然后套用求二元一次方程的方法，

用扩展欧几里得算法求得一组 $x_0$ , $y_0$ 和gcd

long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    long long r=exgcd(b,a%b,y,x);
    y-=x*(a/b);
    return r;
}
long long inverse_element(long long a,long long n)
{
    long long x,y;
    if(exgcd(a,n,x,y)==1ll)
        return (x%n+n)%n;
    else
        return -1;
}

欧拉定理¶

时间复杂度¶

$O(\sqrt n+log_2n)$

原理¶

$a^{-1}\equiv a^{φ(n)-1} \pmod n$

long long euler(long long n)
{
    long long res=n,a=n;  
    for(long long i=2;i*i<=a;i++)
    {  
        if(a%i==0)
        {  
            res=res/i*(i-1);//先除后乘是为了防止中间数据的溢出
            while(a%i==0)
                a/=i;
        }
    }
    if(a>1)
        res=res/a*(a-1);
    return res;
}
long long qpow(long long base,long long power,long long n)
{
    long long result=1;
    while(power>0)
    {
        if(power&1)
            result=result*base%n;
        base=base*base%n;
        power>>=1;
    }
    return result;
}
long long inverse_element(long long a,long long n)
{
    long long ie=qpow(a,euler(n)-1,n);
    if(ie*a%n==1ll)
        return ie;
    else
        return -1;//逆元不存在
}

费马小定理¶

时间复杂度¶

$O(log_2n)$

原理¶

$a^{-1}≡a^{n-2} \pmod n$

long long qpow(long long base,long long power,long long n)
{
    long long result=1;
    while(power>0)
    {
        if(power&1)
            result=result*base%n;
        base=base*base%n;
        power>>=1;
    }
    return result;
}
long long inverse_element(long long a,long long n)
{
    return qpow(a,n-2,n);
}

逆元打表¶

在模质数p下，求1~n逆元, n < p (p是奇质数)

时间复杂度¶

$O(n)$

原理¶

设 $t=M/i$ ， $k=M\%i$

$t*i+k\equiv 0 \pmod M$

$-t*i\equiv k \pmod M$

$-t*inv(k)=inv(i) \pmod M$

$inv(i)=(M-M/i)*inv(M\%i)\%M$

$inv(1)=1$

const int N = 1e5 + 5;
ll inv[N];
    inv[1] = 1;
    for(int i=2; i<=n; ++i)
        inv[i] = (ll) (mod - mod / i) * inv[mod%i] % mod;

任意 n 个数¶

积的逆元等于逆元的积

首先计算 $n$ 个数的前缀积，记为 $s_i$ ，然后用exgcd计算 $s_n$ 的逆元，记为 $sv_n$ 。

因为 $sv_n$ 是 $n$ 个数的积的逆元，所以当我们把它乘上 $a_n$ 时，就会和 $a_n$ 的逆元抵消，于是就得到了 $a_1$ 到 $a_{n-1}$ 的积逆元，记为 $sv_{n-1}$ 。

同理我们可以依次计算出所有的 $sv_i$ ，于是 $a_i^{-1}$ 就可以用 $s_{i-1} \times sv_i$ 求得。

所以我们就在 $O(n + \ln p)$ 的时间内计算出了 $n$ 个数的逆元。

s[0] = 1;
for (int i = 1; i <= n; ++i)
    s[i] = s[i - 1] * a[i] % p;
ll sis = inv(s[n], p);
for (int i = n; i > 1; --i)
{
    inv[i]=sis*s[i-1]%p;
    sis = sis * a[i] % p;
}