a,bZ,且 ab1(modn),则称 ab 关于模 n 互为模逆元(Modular Multiplicative Inverse)

还可记作:b1a(modn)ba1(modn)

模运算的部分性质

(a+b)modn=(amodn+bmodn)modn

(ab)modn=(amodnbmodn+n)modn

(ab)modn=((amodn)(bmodn))modn

abmodn=(amodn)bmodn

上面三条性质,相当于加、减、乘、乘方都齐了,那么除呢?abmodn= ?

这就需要模逆元来解决。

模逆元

类比倒数 ab=1ab1(modn) 也可以称它们互为模倒数(模逆元)

那么如果知道 b 的模逆元为 xabmodc 就可以转化为 (ax)modc

求法

费马小定理 (Fermat's Little Theorem)

p 为质数,整数 ap 互质,则 ap11(modp)

另一种形式:对于任意整数 a,有 apa(modp)

由以上定理:

ap11(modp)

左边提出一个 a

aap21(modp)

因此可得出:

a1ap2(modp)

因此 a 关于模 p 的逆元就是 ap2modp

例如要求 (15/5)mod4,就先求 5 关于 4 的逆元 542mod4=25mod4=1,然后就可以转化为 (15/5)mod4=(151)mod4=3

注意:

  • 满足整数 ap 互质,才存在逆元,否则逆元不存在。
  • p 为质数才可使用费马小定理计算逆元,否则需要使用扩展欧几里得算法求逆元。

快速幂

在实际题目中,模 p 往往非常大,比如为 20220211,那要求一个数的模逆元就会进行一个很大指数运算,因此为了节省时间需要使用快速幂。同时快速幂也兼容取模,因此可以在算幂的同时进行取模运算。

#define MOD 20220211
long long fastpow(long long a, long long b)
{
    a %= MOD; // 开头先取一次模
    long long ans = 1;
    while (b)
    {
        if (b % 2 == 1)
            ans = ans * a % MOD; // 每次运算都取模
        a = a * a % MOD; // 每次运算都取模
        b >>= 1;
    }
    return ans;
}