我的算法书 - 余数、同余与取模

一句话算法

取模就是把整数放到长度为 $m$ 的圆环上，只关心它最后停在哪个位置。

问题模型

给定整数 $a$ 和非零整数 $m$ ，我们希望把 $a$ 写成：

a=mq+r,\quad 0\le r<|m|

其中 $r$ 称为 $a$ 模 $m$ 的非负余数。

在竞赛代码中，取模常用于：

控制答案大小，例如对 $10^9+7$ 取模。
描述循环位置，例如数组下标、钟表、约瑟夫问题。
判断同余关系，例如 $a$ 和 $b$ 除以 $m$ 的余数是否相同。

“同余”

若 $m\mid(a-b)$ ，则称 $a$ 与 $b$ 模 $m$ 同余，记为：

a\equiv b\pmod m

核心直觉

把整数看成在圆环上走路。圆环有 $m$ 个位置：

0 1 2 ... m-1

从 0 出发走 $a$ 步，绕完整圈不改变最终位置，所以只需要保留“不足一圈”的那部分。

以 $m=8$ 为例：

100 = 12 * 8 + 4

所以从 0 顺时针走 100 步，最后停在 4。

逆时针走可以看成走负步数。比如从 0 逆时针走 1 步，就是走 -1 步，在长度为 8 的圆环上最后停在 7。

算法步骤

带余除法

对任意整数 $a$ 和正整数 $m$ ：

找到整数 $q$ ，表示完整走了多少圈。
剩下的部分是：

$r=a-mq$
让 $r$ 落在区间 $[0,m)$ 中。

这个 $r$ 就是规范化后的余数。

C++ 中的规范化取模

C++ 的取余运算结果符号跟被除数有关。因此：

C++ remainder(-1, 8) == -1

但圆环模型中，我们通常希望得到：

-1 mod 8 == 7

竞赛里常用的做法是先取一次 C++ 余数，如果结果为负数，就加上正模数把它拉回 $[0,m)$ 。如果 m 可能为负数，先取绝对值。

圆环移动

若圆环长度为 $n$ ，当前位置为 pos，顺时针走 step 步，其中 step 可以为负数，则新位置是：

\operatorname{norm}(pos+step,n)

其中 $\operatorname{norm}(x,n)$ 表示把 $x$ 规范到 $[0,n)$ 。

算法证明

同余加法

若：

a\equiv a'\pmod m,\quad b\equiv b'\pmod m

则：

m\mid(a-a'),\quad m\mid(b-b')

两式相加：

m\mid((a-a')+(b-b'))

整理：

m\mid((a+b)-(a'+b'))

所以：

a+b\equiv a'+b'\pmod m

这说明加法可以边算边取模。

同余乘法

若：

a\equiv a'\pmod m,\quad b\equiv b'\pmod m

设：

a=a'+km,\quad b=b'+tm

相乘：

ab=(a'+km)(b'+tm)

展开：

ab=a'b'+m(a't+kb'+ktm)

所以：

m\mid(ab-a'b')

即：

ab\equiv a'b'\pmod m

这说明乘法也可以边算边取模。

为什么 C++ 和 Python 的负数取模不同

数学中的带余除法通常要求：

0\le r<|m|

当模数 $m>0$ 时，Python 的取模结果更接近这个非负余数约定。

C++ 整数除法要求商向 0 截断，余数满足：

a=(a/m)\times m+\operatorname{rem}(a,m)

并且余数符号跟 $a$ 相同。

例如 a = 10, m = -7：

C++:    10 = (-1) * (-7) + 3,  所以余数为 3
Python: 10 = (-2) * (-7) - 4,  所以取模结果为 -4

如果竞赛题只关心模 $|m|$ 的圆环位置，推荐统一使用规范化取模，避免被语言细节影响。

复杂度分析

规范化取模只做常数次整数运算：

时间复杂度： $O(1)$ 。
空间复杂度： $O(1)$ 。

同余加法、乘法的每一步取模也是 $O(1)$ 。

代码实现

cpp

        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

        #include <bits/stdc++.h>
using namespace std;

long long normalize_mod(long long a, long long m) {
    m = llabs(m);
    long long r = a % m;
    if (r < 0) r += m;
    return r;
}

long long move_on_circle(long long pos, long long step, long long n) {
    return normalize_mod(pos + step, n);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, m;
    cin >> a >> m;
    cout << normalize_mod(a, m) << '\n';

    long long pos, step, n;
    if (cin >> pos >> step >> n) {
        cout << move_on_circle(pos, step, n) << '\n';
    }

    return 0;
}

测试用例

规范化负数取模

输入：

-1 8

输出：

圆环移动

输入：

10 -7
7 110 8

输出：

3
5

解释：

10 模 7 的圆环位置是 3。
从位置 7 顺时针走 110 步，等价于走 6 步，最后到达位置 5。

应用分类详解

取模的本质是把无限整数压到有限个剩余类中。看到循环、整除、周期、答案很大、下标回绕时，都应该想到取模。

一、答案取模

典型模式： 题目要求输出答案对某个数取模。

识别信号： 出现“答案可能很大”“对 $10^9+7$ 取模”。

核心建模： 利用加法和乘法同余性质，边计算边取模，避免溢出和大整数。

应用场景	经典题目	核心思路
DP 计数	计数类动态规划	每次转移后取模
快速幂	大指数幂取模	乘法边取模
组合数	组合计数	阶乘和逆元都在模意义下维护

二、循环位置

典型模式： 位置在一个环上移动，超过末尾回到开头。

识别信号： 出现“循环队列”“钟表”“约瑟夫问题”“环形数组”。

核心建模： 新位置等于 normalize_mod(pos + step, n)。

应用场景	经典题目	核心思路
约瑟夫问题	Luogu P1996	每次删除后下标在剩余人数中取模
环形数组	数组模拟题	下标移动后规范化
钟表问题	时间计算题	小时、分钟分别对周期取模

三、同余分类

典型模式： 按余数把数分组，统计满足条件的组合。

识别信号： 出现“能被 $k$ 整除”“两数和是 $k$ 的倍数”“余数相同”。

核心建模： 用余数作为桶编号，把整数分到 $0..k-1$ 的桶里。

应用场景	经典题目	核心思路
两数和整除	配对计数题	余数 $r$ 与 $k-r$ 配对
前缀和同余	子数组和整除	前缀余数相同则区间和可整除
周期状态压缩	模周期模拟	状态按余数循环

四、负数取模修正

典型模式： 公式里会出现减法，导致中间结果为负。

识别信号： 出现 a-b 后再取模，或有逆向移动。

核心建模： 每次需要作为数组下标或圆环位置时，使用规范化取模。

经典例题

1. Luogu P1996 约瑟夫问题

每次从当前人开始数，删除后下一个位置仍在一个变短的圆环上。核心是理解“越过末尾回到开头”的取模下标。

2. CSP-S 2023 密码锁

密码位可以循环变化，数字轮从 9 再转会回到 0。核心是把每一位看成长度为 10 的圆环。

3. 子数组和能被 K 整除

若两个前缀和模 $k$ 的余数相同，它们的差就能被 $k$ 整除。核心是按前缀余数分桶计数。

参考

本书整除章节：math/numberTheory/divisible/index.md
本书快速幂章节：math/quick_pow/index.md