模运算中的倒数 - 乘法逆元

a % b 是求 a / b 的余数,这种运算叫做模运算,模运算是数论中的一个很重要的内容。

逆元的意义

我们知道,在模运算中,有以下公式成立:
(a + b) % m == ((a % m) + (b % m)) % m
(a - b) % m == ((a % m) - (b % m)) % m
(a * b) % m == ((a % m) * (b % m)) % m
这三个公式有什么用呢?就是在计算结果灰常灰常大的时候,我们只需要得到它对某个数(比如1,000,000,007)的余数即可,这种情况下,如果计算过程中的数不是很大,而且只有加法减法乘法,那我们就可以在计算过程中不断取余,这样得到的结果也是正确的。
这就造成了一件很尴尬的事,假如计算过程中出现除法该怎么办,要知道上述规律对于除法是不成立的!
在数学运算中:a / b == a * (1 / b),其中1 / bb倒数。那么在模运算中,有没有这种类似于倒数的存在呢?答案是有!它就是乘法逆元

如何计算逆元

方法一扩展欧几里德算法
如果你还不了解扩展欧几里德算法,可以看其他方法,也可以移步这里《求解最大公约数 - 欧几里德算法》简单了解一下。
我们知道扩展欧几里德算法除了可以计算出ab的最大公约数d以外,还能求出a * x + b * y = d的整数解。
如果存在等式a * p - m * q == 1,那么此时(a * p) % m == 1,于是p就是整数a对于整数m的逆元。而这个等式可以很简单的套入扩展欧几里德算法中求解,于是求逆元的代码如下:(C++语言,其中exgcd(int, int, int &, int, int)的实现见《求解最大公约数 - 欧几里德算法》

int mod_inverse(int a, int m)
{
    int d, p, q;
    exgcd(a, m, d, p, q);
    return (p % m + m) % m;
}

这个算法的的时间复杂度和扩展欧几里德算法的时间复杂度一样,都是O(logN)。同时我们也很容易看出来,当am的最大公约数不等于1时,逆元不存在。

方法二:不知道什么名的推导
这个方法是上次从胡光大牛那里学来的,很流弊,很好用,简单记载于此。
我们还是要求a相对于m的逆元a',这里a < m
此时存在k * a + q == m,即k * a + q ≡ 0 (mod m),这里k = ⌊m / a⌋, q = m % a。(是同余符号)
在等式两边同时乘以a' * q',其中a'a的逆元,q'q的逆元,得到:k * q' + a' ≡ 0 (mod m)
移项得a' = -k * q',这里于是代码如下:(C++语言)

int mod_inverse(int a, int m)
{
    if(a == 0) return -1;  // can not found a mod inverse number
    if(a == 1) return 1;
    int ret = mod_inverse(m % a, m);
    if(ret == -1) return ret;
    return (-m / a * ret % m + m) % m;
}

这个算法的复杂度是O(logN)的,我们还可以在O(m)的时间内递推出1,2,3...m的逆元,代码如下:

inv[0] = -1;
inv[1] = 1;
for(int i = 2; i <= m; i++)
{
    if(inv[m % i] == -1) {
        inv[i] == -1);
    } else {
        inv[i] = (-m / i * inv[m % i] % m + m) % m;
    }
}

方法三:费马小定理
费马小定理:若p为素数,则x^p ≡ x (mod p)。(x^pxp次方)
所以x^(p - 1) ≡ 1 (mod p),所以x^(-1) ≡ x^(p - 2) (mod p)x^(-1)即为x的逆元。
所以,当p为素数时,我们可以使用快速幂来很简单的计算出整数x对于p的逆元。

标签: 算法, 数论

添加新评论