同余与模运算

前言

你打开一道算法竞赛题，读完题意，最后一行写着：“答案对 $10^9+7$ 取模。”

这句话几乎出现在每一道计数题里。为什么？因为很多计数问题的答案大得离谱——比如”从 100 个人里选 50 个组成委员会”，答案是 $\binom{100}{50} \approx 10^{29}$，29 位数，long long 存不下。但题目只需要输出它除以 $10^9+7$ 的余数，这个余数在 $0$ 到 $10^9+6$ 之间，轻松存下。

问题是：你不能等算完再取模——那样早就溢出了。你需要在计算的每一步都取模，最终结果还得是对的。

这就需要同余理论。好消息是，模意义下的加法、减法、乘法和你熟悉的普通运算几乎一样——只是每步多加一个 % MOD。但也有陷阱：负数取模、中间值溢出……这些都是竞赛里的常客。

下一篇 02-04 快速幂与逆元 会讲模意义下的乘方和除法（逆元）。

问题的本质

同余：余数相同就是”同类”

今天星期三，10 天后是星期几？$3 + 10 = 13$，$13 \bmod 7 = 6$，星期六。100 天后呢？$3 + 100 = 103$，$103 \bmod 7 = 5$，星期五。

你不关心”过了多少天”，只关心”星期几”——也就是天数除以 7 的余数。10 天和 100 天的余数不同，所以对应不同的星期。但 10 天和 17 天的余数相同（都是 3），所以都是星期六。

这就是同余的直觉：两个数除以 $m$ 的余数相同，它们就是”同类”。数学记号：

$$a \equiv b \pmod{m} \iff m \mid (a - b)$$

比如 $17 \equiv 3 \pmod{7}$，因为 $17 - 3 = 14 = 2 \times 7$。

一个有用的公式：$a \bmod m$ 可以写成 $a - m \cdot \lfloor a/m \rfloor$。这告诉我们：取模本质上就是”减去尽可能多的 $m$“。比如 $17 \bmod 7 = 17 - 7 \times 2 = 3$。

这个公式也解释了为什么负数取模有陷阱：$-3 \bmod 7 = -3 - 7 \times \lfloor -3/7 \rfloor$。这里 $\lfloor -3/7 \rfloor = -1$（向下取整），所以 $-3 - 7 \times (-1) = -3 + 7 = 4$。但 C++ 的 % 对负数的行为是向零取整，$(-3) \% 7 = -3$，不是 4。Python 的 % 则返回非负数，$(-3) \% 7 = 4$。这是语言差异，做题时务必注意。

为什么可以”边算边取模”？

核心性质：同余关系在加法、减法、乘法下保持。 也就是说：

$$\text{如果 } a \equiv a' \pmod{m},\ b \equiv b' \pmod{m}$$ $$\text{那么 } a+b \equiv a'+b' \pmod{m}$$

减法和乘法同理。

这意味着：你可以在计算的任何一步把大数替换成它除以 $m$ 的余数，不影响最终结果的余数。先取模再算和先算完再取模，余数一样。

但前提是：只有加、减、乘。除法不行——下一篇讲。

更具体地说，以下操作不能直接套用同余替换：

操作	能否替换	反例
$a + b$	✅	—
$a - b$	✅	—
$a \times b$	✅	—
$a / b$（整除）	❌	$4/2 \equiv 2, 4/4 \equiv 1$，但 $2 \not\equiv 4 \pmod{3}$，结果不同
$a^n$（$n$ 是常数）	✅	$2^3 \equiv 8 \equiv 1 \pmod{7}$，$9^3 \equiv 729 \equiv 1 \pmod{7}$，$2 \equiv 9 \pmod{7}$，结果一致
$a^b$（$b$ 是变量）	❌	$a_1 = 2, b_1 = 1, a_2 = 2, b_2 = 4$，模 3：$2^1 \equiv 2, 2^4 \equiv 1$，$1 \not\equiv 4 \pmod{3}$ 但结果不同
$a!$（阶乘）	❌	$1! \equiv 1 \pmod{2}$，$3! \equiv 0 \pmod{2}$，$1 \equiv 3 \pmod{2}$ 但阶乘结果不同

记住这张表就能避免踩坑。加、减、乘、常数次幂可以在任何一步取模；除法、变量次幂、阶乘不行。

理论 + 代码

模加法、模减法、模乘法

const long long MOD = 1e9 + 7;

// 模加法
long long add(long long a, long long b) {
    return (a + b) % MOD;
    // a, b 都在 [0, MOD) 内，a+b 最大约 2×10^9，long long 没问题
}

// 模减法
long long sub(long long a, long long b) {
    return (a - b + MOD) % MOD;
    // ① 为什么 +MOD？因为 a-b 可能是负数！
    // C++ 中 (-3) % 7 = -3，不是 4（讲义也特别提醒了这一点）
    // 加一个 MOD 再取模，保证结果非负
}

// 模乘法
long long mul(long long a, long long b) {
    return a * b % MOD;
    // ② a, b 都 < MOD ≈ 10^9，a*b 最大约 10^18
    // long long 最大约 9.2×10^18，刚好没溢出
}

• ① 负数取模是最常见的坑。C++ 的 % 对负数的结果也是负数：$(-3) \% 7 = -3$。但我们需要的是 $[0, m)$ 范围内的余数，即 $(-3) \bmod 7 = 4$（因为 $-3 = -1 \times 7 + 4$）。所以加一个 MOD 再取模：$(-3 + 7) \% 7 = 4\%7 = 4$。即使 a - b 不是负数，加 MOD 再取模也不影响结果（因为 (x + MOD) % MOD = x % MOD）。

• ② 乘法溢出。如果 $a, b$ 都接近 $10^9$，那 $a \times b \approx 10^{18}$。long long 最大 $9.2 \times 10^{18}$，所以刚好没溢出。但如果 MOD 更大（比如 $10^{18}$），乘法就会溢出——那种情况需要 __int128 或特殊处理。

常见陷阱总结

陷阱	错误写法	正确写法	原因
负数取模	(a-b) % MOD	(a-b%MOD+MOD) % MOD	C++ 负数取模得负数
乘法溢出	int a * b	long long a * b	int 只到 $2 \times 10^9$
忘记取模	ans += val	ans = (ans + val) % MOD	不取模就溢出
先乘后除	a * b / c	a / c * b（整除时）	乘完可能溢出

为什么模数总是 $10^9+7$ 或 $998244353$？

计数题末尾那句话——“答案对 $M$ 取模”——里面的 $M$ 几乎总是下面两个数之一：

模数	值	特点
$10^9+7$	1000000007	素数。约 $10^9$，两个模内数之积不超 long long。M&A 演習問題集统一用这个。
$998244353$	998244353	素数。$= 119 \times 2^{23} + 1$，支持 NTT（数论变换），AtCoder ABC/ARC 中极其常见。

它们都是素数，所以每个非零元素都有乘法逆元（下一篇讲）。约 $10^9$ 的大小也刚刚好——足够大避免答案冲突（不同答案对应不同余数），又足够小使得两个模内数之积不超出 long long（$10^9 \times 10^9 \approx 10^{18} < 9.2 \times 10^{18}$）。

实际做题时一定要看清楚题目给的是哪个模数！ 不要想当然地写 const int MOD = 1000000007;——AtCoder ABC 中 $998244353$ 出现频率同样极高（例如 abc456_d Not Adjacent 2）。

本系列例题主要来自 M&A 演習問題集，统一使用 $10^9+7$，所以后续代码中 MOD = 1000000007。但理论完全适用于 $998244353$ 或任何素数模数。

例题

例题 1：M&A 005 — Modulo 100（★1）

题目：给定 $N$ 个整数 $A_1, A_2, \ldots, A_N$，输出它们的和对 100 取模的结果。

数据范围：$1 \le N \le 1000$，$1 \le A_i \le 10^5$

—— AtCoder M&A 005

思路：累加后取模。但更安全的做法是每加一个数就取模——防止 int 溢出。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int sum = 0;
    for (int i = 0; i < N; i++) {
        int a;
        scanf("%d", &a);
        sum += a;
        sum %= 100;    // ① 每加一次就取模，防止溢出
    }
    printf("%d\n", sum);
}

逐行解析：

• ① 如果不取模，$N = 1000$ 个数每个 $10^5$，总和 $10^8 < 2 \times 10^9$（int 范围），这里不会溢出。但养成好习惯：每步取模。

---

例题 2：M&A 049 — Fibonacci Easy (mod 10⁹+7)（★1）

题目：斐波那契数列 $a_1 = 1, a_2 = 1, a_n = a_{n-1} + a_{n-2}$。求 $a_N \bmod (10^9+7)$。

数据范围：$3 \le N \le 10^7$

—— AtCoder M&A 049

思路：递推即可。每步取模 $10^9+7$。$N = 10^7$ 时 $O(N)$ 没问题。

代码：

#include <cstdio>
using namespace std;

const int MOD = 1000000007;

int main() {
    int N;
    scanf("%d", &N);

    int a = 1, b = 1;  // a_1, a_2
    for (int i = 3; i <= N; i++) {
        int c = (a + b) % MOD;  // ① a_n = (a_{n-1} + a_{n-2}) % MOD
        a = b;                   // ② 滚动更新
        b = c;
    }
    printf("%d\n", b);
}

逐行解析：

• ① 取模的位置：在加法之后立刻取模。$(a + b) < 2 \times 10^9$，不超过 int 范围，所以不需要 long long。
• ② 只保留最近两项，空间 $O(1)$。

---

例题 3：M&A 050 — Power（★1）

题目：给定 $a$ 和 $b$，求 $a^b \bmod (10^9+7)$。

数据范围：$1 \le a \le 100$，$1 \le b \le 10^9$

—— AtCoder M&A 050

思路：$b$ 最大 $10^9$，不能循环 $b$ 次。快速幂 $O(\log b)$——这是同余+模运算章节的核心技巧。

代码：

#include <cstdio>
using namespace std;

const long long MOD = 1000000007;

int main() {
    long long a, b;
    scanf("%lld%lld", &a, &b);

    long long base = a, ans = 1;
    while (b > 0) {
        if (b % 2 == 1)                // ① 当前二进制位是 1
            ans = ans * base % MOD;    // ② 乘到结果上
        base = base * base % MOD;      // ③ 底数平方
        b /= 2;
    }
    printf("%lld\n", ans);
}

逐行解析：

• ①②③ 标准快速幂。把 $b$ 写成二进制，逐位处理。每次 base 自乘（平方），如果当前位是 1 就乘到 ans 上。全部取模。

---

例题 4：M&A 053 — Sum of 4^N（★2）

题目：给定正整数 $N$，求 $4^0 + 4^1 + \cdots + 4^N \bmod (10^9+7)$。

数据范围：$1 \le N \le 10^{18}$

—— AtCoder M&A 053

思路：等比数列求和公式：$\sum_{i=0}^{N} 4^i = \frac{4^{N+1} - 1}{4 - 1} = \frac{4^{N+1} - 1}{3}$。

在模 $p$ 下除以 3 等价于乘以 3 的逆元。所以答案 = $(4^{N+1} - 1) \times 3^{-1} \bmod p$。

$4^{N+1}$ 用快速幂，$3^{-1} \bmod p$ 用费马小定理（因为 $p$ 是素数）：$3^{-1} = 3^{p-2} \bmod p$。

代码：

#include <cstdio>
using namespace std;

const long long MOD = 1000000007;

long long power(long long base, long long exp) {
    long long ans = 1;
    while (exp > 0) {
        if (exp % 2 == 1) ans = ans * base % MOD;
        base = base * base % MOD;
        exp /= 2;
    }
    return ans;
}

int main() {
    long long N;
    scanf("%lld", &N);

    long long num = (power(4, N + 1) - 1 + MOD) % MOD;  // ① 分子 = 4^{N+1} - 1
    long long inv3 = power(3, MOD - 2);                  // ② 3 的逆元
    printf("%lld\n", num * inv3 % MOD);                   // ③ 分子 × 逆元
}

逐行解析：

• ① power(4, N+1) - 1：可能变成负数（模运算后），所以 + MOD 再 % MOD 保证非负。
• ② 费马小定理：$3^{-1} \equiv 3^{p-2} \pmod{p}$。
• ③ 模意义下的除法 → 乘以逆元。

---

例题 5：M&A 042 — Sum of Divisors（★2）

题目：设 $f(X)$ 为 $X$ 的正约数个数。求 $\sum_{K=1}^{N} K \times f(K)$。

数据范围：$1 \le N \le 10^7$

—— AtCoder M&A 042

思路：如果对每个 $K$ 单独求 $f(K)$，总时间 $O(N\sqrt{N}) \approx 3 \times 10^{10}$，太慢。换个角度：枚举约数 $d$，看 $d$ 是多少个数的约数——答案 $d$ 的贡献是 $d \times \lfloor N/d \rfloor$（因为 $1$ 到 $N$ 中 $d$ 的倍数有 $\lfloor N/d \rfloor$ 个）。

所以 $\sum_{K=1}^{N} K \times f(K) = \sum_{d=1}^{N} d \times \lfloor N/d \rfloor$。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);

    long long ans = 0;
    for (int d = 1; d <= N; d++) {
        ans += (long long)d * (N / d);  // ① d 的贡献 = d × (1~N中d的倍数个数)
    }
    printf("%lld\n", ans);
}

逐行解析：

• ① 对每个 $d$，$K \in [1, N]$ 中有 $\lfloor N/d \rfloor$ 个数包含 $d$ 作为约数。$d$ 被每个这样的 $K$ 贡献了一次 $K \times d$（不对，更准确地说：$\sum_{K=1}^N K \times f(K) = \sum_{d=1}^N d \times$ ”$d$ 是多少个 $K$ 的约数” $= \sum_{d=1}^N d \times \lfloor N/d \rfloor$）。

验证：$N = 4$。$f(1)=1, f(2)=2, f(3)=2, f(4)=3$。$\sum = 1 + 4 + 6 + 12 = 23$。

用公式：$1 \times 4 + 2 \times 2 + 3 \times 1 + 4 \times 1 = 4 + 4 + 3 + 4 = 15 \ne 23$？

不对！公式应该是 $\sum_{d=1}^{N} d \times$（以 $d$ 为约数的 $K$ 的个数）。但题目是 $\sum K \times f(K)$，不是 $\sum d \times f(d)$。

重新推导：$\sum_{K=1}^N K \times f(K) = \sum_{K=1}^N \sum_{d|K} K = \sum_{d=1}^N \sum_{\substack{K=1 \\ d|K}}^N K$。

对固定的 $d$，$K$ 取 $d, 2d, \ldots, \lfloor N/d \rfloor \cdot d$。所以 $\sum_{d|K} K = d(1 + 2 + \cdots + \lfloor N/d \rfloor) = d \cdot \frac{m(m+1)}{2}$，其中 $m = \lfloor N/d \rfloor$。

代码应该用这个公式。让我重写：

#include <cstdio>
using namespace std;

int main() {
    long long N;
    scanf("%lld", &N);

    long long ans = 0;
    for (long long d = 1; d <= N; d++) {
        long long m = N / d;    // ① d 的倍数有多少个
        ans += d * m * (m + 1) / 2;  // ② d × (1+2+...+m)
    }
    printf("%lld\n", ans);
}

验证：$N = 4$。

• $d=1$: $m=4$, $1 \times 4 \times 5/2 = 10$
• $d=2$: $m=2$, $2 \times 2 \times 3/2 = 6$
• $d=3$: $m=1$, $3 \times 1 \times 2/2 = 3$
• $d=4$: $m=1$, $4 \times 1 \times 2/2 = 4$
• 总计 $10+6+3+4=23$。✓

参考文献

理论讲义 — AtCoder Algorithm Lectures

• 合同式の基礎（難易度 1）

教材讲解 — 競技プログラミングの鉄則 第 5 章

• 5.3 B28 Fibonacci Easy（模运算+递推 解说）

基础练习 — アルゴリズムと数学 演習問題集

• 005 Modulo 100（累加取模）【例题】
• 049 Fibonacci Easy（递推 mod 10⁹+7）【例题】
• 050 Power（A^B mod p）【例题】
• 053 Sum of 4^N（等比数列取模）【例题】
• 042 Sum of Divisors（约数函数求和）【例题】
• 059 Power of Two（2^N的个位，周期性）
• 079 ModSum（最大化余数之和）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化