跳转至

取模意义下的逆元

如果一个线性同余方程 \(ax \equiv 1 \pmod p\) 成立，则称 \(x\) 为 \(a\) 在模 \(p\) 意义下的逆元，记作 \(x=a^{-1}\)。

注意溢出

逆元相关的算法涉及大量的指数和乘法运算，一定要开 long long。

exgcd 求逆元

逆元的定义是一个线性同余方程，我们可以将它转化为一个二元一次不定方程：

\[ ax-py=1 \]

这种方程可以使用扩展欧几里得算法求出一组解 \((x,y)\)，其中的 \(x\) 就是 \(a\) 的一个逆元。

注意，扩欧的 \(O(\log a)\) 时间复杂度是其理论上界。经实测，其具有非常小的常数。

逆元存在定理

\(a\) 在模 \(p\) 意义下（\(1\le a<p\)）存在乘法逆元的充要条件是 \(a\) 与 \(p\) 互质。

费马小定理求逆元

引理

当 \(a\) 与 \(p\) 互质（\(1\le a<p\)）时，\(a,2a,3a,\cdots (p-1)a\) 模 \(p\) 的结果覆盖 \([1,p-1]\) 的所有整数。

证明

假设存在 \(1\le x<y<p\) 满足 \(xa\equiv ya\pmod p\)，那么有 \(p\mid (y-x)a\)。由于 \(a\) 和 \(p\) 互质，因此 \(p\mid y-x\)，显然与 \(1\le x<y<p\) 矛盾。证毕。

费马小定理：若 \(p\) 为质数，\(1\le a<p\)，则

\[ a^{p-1} \equiv 1 \pmod p \]
证明

由引理可得，

\[ (a)(2a)(3a)\cdots\big((p-1)a\big)\equiv (p-1)!\pmod p \]

变形得

\[ (p-1)!a^{p-1}\equiv (p-1)!\pmod p \]

当且仅当 \(p\) 是质数，\((p-1)!\) 的逆元存在。此时有

\[ a^{p-1}\equiv 1\pmod p \]

由此我们可以得到：

\[ a^{p-2}\times a \equiv 1 \pmod p \]

根据定义，\(a^{p-2}\) 正是 \(a\) 的一个逆元。我们可以使用快速幂以 \(O(\log_2{p})\) 的时间复杂度求出。

线性求逆元

例题

给定一个正整数 \(n\) 和一个质数 \(p\)（\(n<p\)），输出所有 \(i\in[1,n]\) 的逆元 \(i^{-1}\)。

\(n\le 3\times 10^6\)

我们必须在 \(O(n)\) 的时间复杂度内求出总共 \(n\) 个数的逆元。对于数字 \(i\)，假如我们已经求出了所有 \(j<i\) 的逆元 \(j^{-1}\)。将质数 \(p\) 对 \(i\) 取模：

\[ p=\lfloor\frac{p}{i}\rfloor\times i+r \]

其中 \(r<i\)；由此得到：

\[ \begin{align*} \lfloor\frac{p}{i}\rfloor\times i+r\equiv 0 \pmod p\\ \lfloor\frac{p}{i}\rfloor\times i\equiv -r \pmod p \end{align*} \]

我们将方程两边同时乘以 \(i^{-1}r^{-1}\)：

\[ i^{-1}\equiv -\lfloor\frac{p}{i}\rfloor\times r^{-1} \pmod p \]

就得到了 \(i\) 的逆元。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int n, p;
int inv[N];

int main() {

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

    return 0;
}

通过这种方法，我们做到可以 \(O(n)\) 预处理，\(O(1)\) 求出组合数 \(\binom{a}{b}\)，\(a,b\le n\)。

质因子分离法 / 模数不是质数

这种方法能实现对一个数字进行累乘、累除且模数 \(p\) 不是质数的情况。

我们先对 \(p\) 进行质因子分解；每次操作都将操作数 \(x\) 中所有 \(p\) 的质因子单独分离出来，单独处理；剩下的数一定和 \(p\) 互质，可以使用 exgcd 求出逆元。

代码 
 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
int notPri[P], pri[P], pcnt;

// 筛出 [1,n] 区间内的所有质数
void prime() {
    for(int i = 2; i <= p; i++) {
        if(!notPri[i]) pri[++pcnt] = i;
        for(int j = 1; j <= pcnt; j++) {
            if(i * pri[j] > p) break;
            notPri[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}

// 快速幂
int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

// 扩欧求逆元
void exgcd(const int &a, const int &b, int &x, int &y, int &d) {
    if(b == 0) {
        x = 1, y = 0;
        d = a;
        return;
    }
    exgcd(b, a % b, y, x, d);
    y -= a / b * x;
}

// 互质逆元
int inv(int a) {
    int x, y, d;
    exgcd(a, p, x, y, d);
    if(d != 1) throw "gcd(a, p) != 1";
    x = (x % p + p) % p;
    return x;
}

// pp[i] 储存 p 的质因数分解结果
// cnt[i] 表示质因子 pri[pp[i]] 的幂次
// num 表示跟 p 互质的那部分是多少
int pp[50], ppcnt;
int cnt[50], num = 1;

// 乘法
void mul(int x) {
    for(int i = 1; i <= ppcnt; i++) {
        while(x % pri[pp[i]] == 0) {
            x /= pri[pp[i]];
            cnt[i]++;
        }
    }
    num = num * x % p;
}

// 除法
void div(int x) {
    for(int i = 1; i <= ppcnt; i++) {
        while(x % pri[pp[i]] == 0) {
            x /= pri[pp[i]];
            cnt[i]--;
        }
    }
    num = num * inv(x) % p;
}

// 返回结果
int calc() {
    int res = 1;
    for(int i = 1; i <= ppcnt; i++) {
        res = res * qpow(pri[pp[i]], cnt[i]) % p;
    }
    res = res * num % p;
    return res;
}