算法竞赛中的取模运算

在算法竞赛中，为了防止溢出和确保结果在合理范围内，通常使用取模运算。常见的模数是 $ = 1,000,000,007 $（一个大质数）。下面是一些常用的取模操作及其示例：

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
const int MOD = 1'000'000'007;

// 加法
int add(int a, int b) {
    return (a + b) % MOD;
}

// 减法
int subtract(int a, int b) {
    return (a - b + MOD) % MOD;
}

// 取模到 [0, MOD-1] 中，无论正负
int mod(int a) {
    return (a % MOD + MOD) % MOD;
}

// 乘法
int multiply(int a, int b) {
    return (1LL * a * b) % MOD;
}

// 多个数相乘，要步步取模，防止溢出
int multiply(int a, int b, int c) {
    return (1LL * a * b % MOD * c) % MOD;
}

// 快速幂（计算 a^b % MOD）
int qpow(int a, int b, int mod) {
    int res = 1;
    while (b > 0) {
        if (b & 1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return res;
}

// 除法（MOD 是质数且 b 不是 MOD 的倍数）
int divide(int a, int b) {
    return 1LL * a * qpow(b, MOD - 2, MOD) % MOD;
}

详细解释

  1. 加法

    \((a + b) \% \text{MOD}\)

    将两个数相加后取模。

  2. 减法

    \((a - b + \text{MOD}) \% \text{MOD}\)

    先进行减法运算，再加上 MOD 防止出现负数，最后取模。

  3. 取模到 [0, MOD-1]

    \((a \% \text{MOD} + \text{MOD}) \% \text{MOD}\)

    无论 a 是正数还是负数，结果都被规范到 [0, \(\text{MOD}-1\)] 的范围内。

  4. 乘法

    \(a \times b \% \text{MOD}\)

    将两个数相乘后取模。需要注意的是为了防止溢出，通常在 C++ 中用 1LL * a * b 将运算提升到长整型。

  5. 多个数相乘

    \(a \times b \% \text{MOD} \times c \% \text{MOD}\)

    逐步取模，防止中间结果溢出。

  6. 快速幂

    \(\text{qpow}(a, b, \text{MOD})\)

    快速幂算法用于计算 \(a^b \% \text{MOD}\) ，时间复杂度为 \(O(\log b)\) 。

  7. 除法

    \(a \times \text{qpow}(b, \text{MOD} - 2, \text{MOD}) \% \text{MOD}\)

    当 MOD 是质数时，利用费马小定理 $ b^{-1}  (  )$ ，求出 $b^{-1} b^{-2}  (  ) $，从而实现除法。