前往 算竞题解 分类 || 前往 算竞模板 分类

简介

本文包括：费马小定理求逆元、扩展欧几里得算法求逆元、线性递推求逆元。

三者的区别

费马小定理求逆元：要求模是质数，复杂度 O(log⁡2n)O(\log_2{n})，最常用。

扩展欧几里得算法求逆元：不要求模是质数，复杂度 O(log⁡n)O(\log{n})。

线性递推求逆元：线性求出所有逆元，复杂度 O(n)O(n)。

模板题链接

下方模板自取，相关证明见下方链接相关题解。

洛谷 P3811 【模板】乘法逆元

费马小定理求逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 费小求逆元. 要求模是质数. 依赖: quick_pow. 复杂度: O(log(MOD)).
const int MOD = 1000000007;

// 快速幂
int quick_pow(int base, int exponent) {
    int res = 1 % MOD;
    base %= MOD;
    while (exponent) {
        if (exponent & 1)
            res = res * base % MOD;
        base = base * base % MOD;
        exponent >>= 1;
    }
    return res;
}

// 费马小定理求逆元
inline int inv(int primal) { return quick_pow(primal, MOD - 2); }

扩展欧几里得算法求逆元

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
// 扩欧求逆元. 不要求模是质数. 复杂度: O(log(modulo))
const int MOD = 1000000007;

// 扩展欧几里得
int _exgcd(int a, int b, int &x, int &y) {
    int d = a;
    if (b != 0) {
        d = _exgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}
inline bool exgcd(int a, int b, int c, int &x, int &y) {
    int _x, _y, g;
    g = _exgcd(a, b, _x, _y);
    if (c % g) return false;
    int p = b / g;
    x = (c / g * _x % p + p) % p;
    y = (c - a * x) / b;
    return true;
}

// 线性同余方程
inline int linear_congruence_theorem(int a, int c, int m) {
    int x, y;
    bool flag = exgcd(a, m, c, x, y);
    return flag ? x : -1;
}

// 扩展欧几里得求逆元
inline int inv(int primal) { return linear_congruence_theorem(primal, 1, MOD); }

线性递推求逆元

1
2
3
4
5
6
7
// 线性递推求逆元. 要求模是质数. 求 [1, range] 所有数的逆元. 复杂度: O(range).
const int MOD = 1000000007;
void inv_liner(int range, int modulo, int res[]) {
    res[1] = 1;
    for (int i = 2; i <= range; i++)
        res[i] = (modulo - modulo / i) * res[modulo % i] % modulo;
}