时间戳

首页 > 技术文章 > 【数学】乘法逆元（扩展欧几里得算法、裴蜀定理、费马小定理、欧拉定理）

【数学】乘法逆元（扩展欧几里得算法、裴蜀定理、费马小定理、欧拉定理）

Tshaxz 2021-08-27 12:52 原文

取模运算的性质

image
But：

image

乘法逆元

在算法竞赛中，经常会遇到求解数据很大，则输出模 \(10^9+7\) 的解这类要求。加法、减法、乘法等操作，基于同余理论直接取模即可。但遇到除法时，某步中间结果不一定能完成整除，就无法求解了。所以引入了乘法逆元。

从网上找了几种不同的定义：
定义1：
image
定义2：
image
核心思想就是：除以一个数等于乘上这个数的倒数，在除法取余的情况下，就是乘上这个数的逆元
即有：
\(\frac{a}{b}\% p = (a \times b^{-1}) \%p= ((a\%p) \times (b^{-1}\%p))\%p\)
这样就可以把除法转换为乘法。
求组合数的时候会用到。

求逆元的方法：
1.扩展欧几里得算法（通解）
2.费马小定理（只有当模数为质数时才可以用）

1.扩展欧几里得算法求逆元

image
其中整数x,y的计算方法被称为扩展欧几里得算法。

上面的Bezout定理又称裴蜀定理：
image

扩展欧几里得算法代码：

int exgcd(int a,int b,int &x,int &y)
{
    if(!b) //如果b是0
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x); // by + (a % b) * x = d ,d为(a,b)的最大公约数
    y -= a / b * x; //公式化简
    return d;
}

简要证明：
由欧几里得算法：gcd(a,b) = gcd(b, a % b)
设d = gcd(a,b) = gcd(b, a % b)
由裴蜀定理：
\(yb + x(a \%b) = d\)
\(yb + x(a - \lfloor \frac{a}{b} \rfloor b) = d\)
\(yb + xa - \lfloor \frac{a}{b} \rfloor bx = d\)
\(ax + b(y - \lfloor \frac{a}{b} \rfloor x) = d\)
所以：
\(x' = x\)
\(y' = y - \lfloor \frac{a}{b} \rfloor x\)

image
求出 \(x\)就得到了 \(a\) 关于模 \(b\) 的逆元。

时间复杂度\(O(logn)\)
适用范围：存在逆元即可求，适用于个数不多但模数很大的时候，最常用、安全的求逆元方式。

2.费马小定理求逆元（模数为质数时可用）

费马小定理是欧拉定理的特殊情况。
版本1：：
image
版本2：（版本1两边同除\(a\)即为版本2）
image

对于版本2，继续往下推一步即可得出结论：
image
两边同除\(a\)
image
所以\(a^{p-2}\)就是\(a\)模\(p\)的逆元。
然后快速幂求一下就可以了。
快速幂：

int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

参考：
https://zhuanlan.zhihu.com/p/378728642
https://article.itxueyuan.com/ZoGkvE
《算法竞赛进阶指南》李煜东 著

推荐阅读