『同余乘法逆元』

By | 2019年4月25日


乘法逆元

我们知道,由于同余的运算只定义在整数集中,而整数集不满足除法封闭,所以同余是不满足同除性的。但是,如果有涉及取模操作的计数类题目当中需要除法运算怎么办,这就需要乘法逆元了。

定义

若整数\(b,m\)互质,且\(b|a\),则存在一个整数\(x\),满足\(\frac{a}{b}\equiv ax(mod\ m)\),称\(x\)\(b\)在模\(m\)意义下的乘法逆元,即为\(b^{-1}(mod\ m)\)

通常来说,我们会使用另一种方式来表示逆元:
\[\frac{a}{b}\equiv ab^{-1}\equiv \frac{a}{b}*b*b^{-1}(mod\ m)\]
故对于逆元\(b^{-1}(mod\ m)\),满足\(b*b^{-1}\equiv 1(mod\ m)\)

求解

了解了模意义下乘法逆元的定义和作用,那么我们需要知道如何求解。通常来说,我们有好几种常用的方式,如费马小定理,扩展欧几里得等,接下来我们一一详解。

费马小定理

\(p\)为质数,则对于任意整数\(a\),有\(a^p\equiv a(mod\ p)\)

注意到著名的费马小定理和我们的逆元非常像,可以推导一下:
\[
a^p\equiv a(mod\ p)
\\a^{p-1}\equiv 1(mod\ p)
\\a*a^{p-2}\equiv 1(mod\ p)
\]

所以,当模数\(p\)为质数时,\(a^{p-2}\)就是\(a\)在模\(p\)意义下的乘法逆元。

\(a^{p-2}\)显然是可以用快速幂算的,那么我们就得到了逆元的第一种解决方案,可以求解单独一个数的逆元,时间复杂度为\(O(log_2p)\)

\(Code:\)

inline long long power(long long a,long long b,long long p)
{
    long long res=1;
    while (b)
    {
        if (1&b)res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
inline long long Fermat(long long a,long long p)
{
    return power(a,p-2,p);
}

欧拉定理

若正整数\(a,p\)互质,则\(a^{?(p)}≡1(mod\ p)\)\(?(p)\)为欧拉函数。

费马小定理求逆元的话是要求模数\(p\)为质数的,更一般地,如果只能保证\(a,p\)互质,那么我们可以用欧拉定理求逆元。
\[
a^{\phi(p)}\equiv 1(mod\ p)
\\a*a^{\phi(p)-1}\equiv 1(mod\ p)
\]

那么\(a^{\phi(p)-1}\)就是\(a\)在模\(p\)意义下的一个乘法逆元。

欧拉函数可以用试除法分解质因数求,那么这就是求解逆元的第二种方法,可以求解单独一个数的逆元,时间复杂度\(O(\sqrt p+log_2p)\)

\(Code:\)

inline long long power(long long a,long long b,long long p)
{
    long long res=1;
    while (b)
    {
        if (1&b)res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
inline long long phi(long long x)
{
    long long ans=x;
    for (long long i=2;i*i<=x;i++)
    {
        if (x%i==0)
        {
            ans=ans/i*(i-1);
            while (x%i==0)x/=i;
        }
    }
    if (x>1)ans=ans/x*(x-1);
    return ans;
}
inline long long Eular(long long a,long long p)
{
    return power(a,phi(p)-1,p);
}

线性同余方程

我们已经知道了只有\(a,p\)互质时逆元\(a^{-1}\)的求法,但是试除法求解欧拉函数未免有点慢。考虑到我们已经得到了逆元的表达方式,其实我们可以直接通过解线性同余方程的方法入手,求解逆元。

已知逆元\(a^{-1}(mod\ p)\)满足\(a*a^{-1}\equiv 1(mod\ p)\),令\(x=a^{-1}\),则\(ax\equiv 1(mod\ p)\)

这是一个简单的线性同余方程,设\(-py=ax-1\),则可以将方程改写为\(ax+py=1\),利用扩展欧几里得算法找到解。

这就是求解逆元的第三种方法,以求解单独一个数的逆元,时间复杂度\(O(log_2a+log_2p)\)

\(Code:\)

inline long long Exeuclid(long long a,long long &x,long long b,long long &y,long long c)
{
    if (!b){x=c/a,y=0;return a;}
    else
    {
        long long p=Exeuclid(b,x,a%b,y,c);
        long long x_=x,y_=y;
        x=y_,y=x_-a/b*y_;
        return p;
    }
}
inline long long Euclid(long long a,long long p)
{
    long long x_,y_;
    Exeuclid(a,x_,p,y_,1);
    return (x_+p)%p;
}

逆元递推

如果求的是单独一个数的逆元的话,那么以上的算法基本上可以完美解决了。现在,如果需要快速的求解\(1-n\)每一个数模\(p\)意义下的逆元,我们就需要要到逆元递推了。

引理:\(x^{-1}=(p-\frac{p}{x})*(p\ mod\ x)^{-1}\ mod\ p\)

证明:

\(t=\lfloor \frac{p}{x} \rfloor\)\(k=p\ mod\ x\),即\(p=tx+k\)

那么显然有\(tx+k\equiv 0(mod\ p)\),则\(-tx\equiv k(mod\ p)\)

将上式两边同时除以\(x*k\),则\(-t*k^{-1}\equiv x^{-1}(mod\ p)\),进而得到\(x^{-1}=(p-\frac{p}{x})*(p\ mod\ x)^{-1}\ mod\ p\)

已知\(1^{-1}=1\),那么剩下的递推就行了,可以求解\(1-n\)所有数的逆元,时间复杂度\(O(n)\)

\(Code:\)

inline long long recursion(int n)
{
    inv[1]=1;
    for (int i=2;i<=n;i++)
        inv[i]=(p-p/i)*inv[p%i]%p;
}

逆元递归

当然,利用上述引理,我们也可以直接递归来求解单独一个数的逆元,时间复杂度为\(O(log_2a)\)

\(Code:\)

inline long long inv(long long x,long long p)
{
    if (x==1)return 1;
    else return (p-p/x)*inv(p%x)%p;
}

总结

至此,本文已经介绍了\(5\)种求乘法逆元的方案,其中每一种方法都有各自的优缺点,希望读者能够灵活运用,选择合适的方法来求解逆元。



注:www2014.aspxhtml.com转载自cnblogs,若看不到图片,请移步来源网址查看。
via:https://www.cnblogs.com/Parsnip/p/10698402.html

发表评论

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