乘法逆元

定义

设模数为m，对于一个整数a，如果存在另一个整数$a^ {-1} (0 < a^ {-1} <m)$，满足$a*a^{-1}\equiv 1(\bmod m)$，则称$a^{-1}$是a的乘法逆元。
一个数有逆元的充分必要条件是$gcd(a,m)=1$，此时逆元唯一存在。
逆元的含义：模m意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

如何求乘法逆元

1.m为质数

定义式可以转化为$a*a^{-1}=km+1$，即$a^{-1}*a-k*m=1$，根据裴蜀定理，gcd(a, m)=1，必然存在整数$a^{-1}$和k使得上式成立。
如果$(a_0^{-1}, k_0)$是一组解，那么$(a_0^{-1}+cm, k_0+ca),c\in Z$都是上式的解。因此必然存在一组解中的$a_0^{-1}$满足$0<a_0^{-1}<m$，即为所求的$a^{-1}$。

可以使用费马小定理求$a^{-1}$，即

$a^{m-1}\equiv1(\bmod m)$

进一步有

$\begin{aligned} &a^{m-1}a^{-1}\equiv a^{-1}\\ \Leftrightarrow &a^{m-2}aa^{-1}\equiv a^{-1}(\bmod m)\\ \Leftrightarrow &a^{m-2}\equiv a^{-1} \end{aligned}$

因此，$a^{-1}$就等于$a^{m-2}$对m取模的结果。计算$a^{m-2}$可以使用快速幂取模，在$O(logm)$时间内完成。

2.m不为质数

不管m是否为质数，都可以使用扩展欧几里得计算$a^{-1}$：
给定模数m，求解$a^{-1}\cdot x \equiv 1(\bmod m)$可以转化为$a\cdot x - m\cdot y=1$
然后可以套用求二元一次方程的方法，用扩展欧几里得算法求逆元，复杂度为$O(logm)$。

在使用扩展欧几里德算法求解逆元前，首先通过证明扩展欧几里得算法来对该算法有一个简单的理解：
引理：存在 x , y 使得 gcd(a,b)=ax+by
证明：

当 b=0 时，gcd(a,b)=a，此时 x=1 , y=0

当 b!=0 时，

设 $ax1+by1=gcd(a,b)=gcd(b,a\bmod b)=bx2+(a\bmod b)y2$

又因 $a\bmod b=a-\frac{a}{b}*b$ ，可得：
$ax1+by1=bx2+(a-a/b*b)y2$
$ax1+by1=bx2+ay2-a/b*by2$
$ax1+by1=ay2+bx2-b*a/b*y2$
$ax1+by1=ay2+b(x2-a/b*y2)$

解得 $x1=y2$ , $y1=x2-a/b*y2$
因此当 b=0 时存在 x , y 为最后一组解
而每一组的解可根据后一组得到
所以第一组的解 x , y 必然存在

根据上面的证明，在实现的时候采用递归做法
先递归进入下一层，等到到达最后一层即 b=0 时就返回x=1 , y=0
再根据$x1=y2 , y1=x2-a/b*y2$ ( x2 与 y2 为下一层的 x 与 y ) 得到当层的解
不断算出当层的解并返回，最终返回至第一层，得到原解

由于gcd(a, m)为1，引理转化为ax+by=1，可以使用扩展欧几里德算法求逆元，过程如下：求exgcd(a, m)—>利用欧几里得算法不断递归直到x=1,y=0—>反向递归求出第一层的x和y，x即为a在模m意义下的的逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public static long exgcd(long a, long b, MyLong x, MyLong y) {
    if(b == 0) {
        x.v = 1;
        y.v = 0;
        return a;
    }
    long gcd=exgcd(b, a%b, x, y);
    long c = y.v;
    y.v = x.v - (a/b)*y.v;
    x.v = c;

    return gcd;
}
// 由于java没有指针，创建一个自定义类方便操作
class MyLong{
    long v;
    public MyLong() {};
    public MyLong(long v) {
        this.v=v;
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long a = sc.nextLong();
    long m = sc.nextLong();

    MyLong y = new MyLong();
    MyLong x = new MyLong();
    long inv = (exgcd(a, m, x, y) == 1 ? (x.v % m + m) % m : -1);	// 求a关于m的逆元
}

简单总结

• 乘法是遵循取模定理的，即$(a\times b) \bmod m=((a\bmod m)\times (b\bmod m)) \bmod m$，但是除法不遵循，计算$a/b \bmod m$，不能对a和b分别取模再相除。要用乘法逆元，即$\frac{a}{b} \equiv a\cdot b^{-1}(\bmod m)$，把除法转化为模m乘法，然后就可以把$a/b \bmod m$转化为$a*x \bmod m $。
• 一般如果$m$是质数，求$x$可以用费马小定理，$b^{m-2}$就是$x$。求幂的时候需要用快速幂取模。
• 无论$m$是否为质数，都可以用扩展欧几里得算法计算逆元。

模板

求逆元多出现在组合数学，需要对答案取模的题目中，这种情况下一般需要求某些数关于模数m的逆元。
可以用递推的方式预处理出所有数的阶乘以及阶乘的逆元，如下代码所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    private static final int MOD = (int)1e9 + 7;
    private static final int MX = (int)1e5 + 1;

    // 组合数模板
    static final long[] FAC = new long[MX];     // FAC[i]表示i!
    static final long[] INV_FAC = new long[MX]; // INV_FAC[i]表示i!在MOD下的逆元，即1/(i!)

    static{
        FAC[0] = 1;
        for(int i = 1;i < MX;++i){
            FAC[i] = FAC[i-1] * i % MOD;
        }
        INV_FAC[MX-1] = myPow(FAC[MX-1], MOD-2);
        for(int i = MX-1;i >= 1;--i){
            INV_FAC[i-1] = INV_FAC[i] * i % MOD;
        }
    }

    // 组合数公式，n个里面选k个
    private static long comb(int n, int k){
        return FAC[n] % MOD * INV_FAC[n-k] % MOD * INV_FAC[k] % MOD;
    }

    // 快速幂+取模
    private static long myPow(long x, int p){
        long ret = 1;
        while(p > 0){
            if(p % 2 == 1) ret = ret * x % MOD;
            x = x * x % MOD;
            p >>= 1;
        }
        return ret;
    }
}

题目

2954. 统计感冒序列的数目 - 力扣（LeetCode）(内有组合数学模板)

1916. 统计为蚁群构筑房间的不同顺序 - 力扣（LeetCode）

__END__