C++ 算法考级专栏
🎨 视觉封面【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:同余定理与取模铁律——为什么减法取模要先 +MOD,而除法绝对不能直接取模?
在信奥赛场上,几乎每一道递推计数、动态规划或数论求值题的末尾都会印着那句熟悉的提示:“由于答案可能很大,请输出答案对 (即 1000000007)取模后的结果。” 许多同学看到这句话暗自窃喜,以为只要在 cout 输出前顺手补一个 % MOD 就万事大吉;殊不知评测结果出来却是一片刺眼的 WA(答案错误):有人在循环里一路累加累乘,没等走到输出语句就已经撑爆 long long 溢出回绕;有人在前缀和作差时写了 (pre[r] - pre[l - 1]) % MOD,莫名其妙吐出一串负数;更有人在计算组合数或等差求和公式 时,天真地写下 ((n % MOD) * ((n + 1) % MOD) / 2) % MOD,掉进了“除法直接取模”的致命深渊!在 GESP 五级认证以及 CSP-J/S 初赛与复赛中,同余关系 的代数性质、加减乘“边算边模”防溢出公式、C++ 负数取模向零截断机制与 + MOD 扶正铁律,以及除法不满足取模分配律的破局之道,是决定计数与数论题能否稳拿满分的基本功。本文将带你从底层数学与编译器行为出发,把取模运算的所有暗礁一次性彻底扫清。
🎯 考纲锚点与核心痛点
📍 对应考点:深入理解初等数论中的同余概念 及其基本性质,熟练掌握模意义下加法、减法与乘法的同余保持律与防溢出编码规范,厘清 C++
%运算符对负数的处理机制及模意义下除法的禁忌。 🎯 适用等级:GESP 五级考点 | CSP-J/S 初赛/复赛必考
在考场实战与初赛阅读程序题中,考生最容易在以下三大痛点上丢分:
- “攒到最后才取模,中途早已溢出变质”:误以为同余只管最终结果,在连乘或递推中途不取模,或者两个
int变量做(a * b) % MOD时漏写1LL *强制类型提升,导致乘积在进入%运算前就已经在 32 位寄存器里溢出截断,神仙难救; - “混淆数学最小非负余数与 C++ 负数取模,减法算出一堆负值”:当两个取过模的数相减(例如前缀和
pre[r] - pre[l - 1])时,即使原区间和明明是正数,取模后的pre[r]也完全可能小于pre[l - 1],直接% MOD会保留负号输出负数; - “把四则运算一视同仁,对着除法强行套用取模分配律”:看到加、减、乘都能拆开各自
% MOD,便想当然地认为(a / b) % MOD等于((a % MOD) / (b % MOD)) % MOD,在涉及除以2、除以阶乘的公式里全盘算错!
🧠 一、 核心原理深度拆解(有理论)
1. 同余关系的本质:“余数时钟环”与等价类
给定一个正整数模数 (),如果两个整数 和 除以 所得的最小非负余数完全相同(或者等价地说,它们的差 能够被 整除,记作 ),我们就称 与 模 同余,记作:
我们可以把模 的世界想象成一座只有 0, 1, 2, ..., m - 1 共 个刻度的环形时钟(以 的星期时钟为例):
================================================================================
【模 m = 7 的“余数时钟环”与数轴折叠映射图】
真实整数数轴: ... -10 -9 -8 | -3 -2 -1 | 0 1 2 ... 11 12
│ │ │ │ │ │ │ │ │ │ │
每次跨过 ±7 绕环一圈 ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼
模 7 最小非负余数: [4] [5] [6] [4] [5] [6] [0] [1] [2] ... [4] [5]
▶ 同余本质:-10、-3、4、11 虽然大小悬殊,但两两之差都是 7 的整数倍,
在模 7 时钟环上全都精准落在同一个刻度【4】上!
即:-10 ≡ -3 ≡ 4 ≡ 11 (mod 7)
================================================================================同余关系天生具备与等号 = 极为相似的三大等价性质:自反性()、对称性(若 则 )和传递性(若 且 ,则 )。
2. 四则运算同余铁律:为什么加减乘都能拆,唯独除法绝对不行?
设整数 ,(其中 ,)。我们用最直观的代数展开来看看四则运算在模 下会发生什么:
-
加法同余律(成立 ✅): 整倍数的 在除以 时直接化为
0消去! -
减法同余律(数学成立,代码需防负 ✅):
-
乘法同余律(成立 ✅): 展开式中前三项全都带有因子 ,对 取模瞬间灰飞烟灭,只剩余数之积 !这就是为什么成千上万步的加法和乘法,每一步都可以放心地把大数直接替换成它的余数(“边算边取模”),而最终余数丝毫不差!
-
除法同余分配律(绝对不成立 ❌): 为什么除法会彻底失效?请看一个一秒击碎幻想的反例:设 。
- 真实结果:先做整除 ,再对 取模得 ;
- 错误拆模:若先对分子分母分别取模,,,相除变成 (整数除法截断)!
4瞬间变成了0! - 底层根源:在 中,当你除以 时, 不一定是 的整数倍(因为 可能会把模数 旁边的系数 约掉一部分,改变除以 的余数)!
- 考场破局正道:在 GESP 五级与 CSP-J 阶段(未涉及费马小定理与乘法逆元时),遇到模意义下的除法(如 或小组合数),必须在取模之前利用因数整除性质先把分母彻底约掉,化为纯乘法后再取模!
3. C++ 负数取模陷阱与四则安全取模标准速查表
在数论定义中,任何整数除以正整数 的余数都规定落在非负区间 内(例如 ,数学余数为 4)。
但在 C++11 标准中,整数除法 a / m 严格采用向零截断(Truncate toward zero),并强制满足恒等式 (a / m) * m + (a % m) == a。这意味着:C++ 中 a % m 的正负号永远跟着被除数 a 走!
- 计算
-10 / 7:商向零截断为-1(而非-2); - 计算
-10 % 7:余数为-10 - (-1) * 7 = -3(落在了[-(m - 1), 0]区间)!
怎样把可能为负的 C++ 余数统一拉回标准非负区间 ?只需在时钟环上顺时针拨一圈(+ m),再对 m 取一次模防止原本就是正数时越界(例如 (4 + 7) % 7 = 4,(-3 + 7) % 7 = 4)!由此得到全场景通用的四则取模标准范式表:
| 运算场景 | 数学目标(结果归入 ) | 错误高危写法(考场重灾区) | C++11 满分安全写法(设 M = MOD) |
|---|---|---|---|
| 单数归一化 | ( 可能为负) | a % M( 时得负数) |
(a % M + M) % M |
| 模加法 | (a + b) % M(a+b 可能爆 int) |
((a % M) + (b % M)) % M(推荐 long long) |
|
| 模减法 | (a - b) % M(余数相减极易为负) |
((a - b) % M + M) % M |
|
| 模乘法 | (a * b) % M(两 int 相乘先溢出) |
(1LL * (a % M) * (b % M)) % M |
|
| 含除整式 | ((k % M) * ((k+1) % M) / 2) % M |
先挑 中的偶数 / 2,再各自 % M 相乘 |
💡 考场黄金法则(背诵直接套用):
- 【加乘边算边模,
1LL护航防爆】:只要题目要求对MOD(如 )取模,加法和乘法必须每算一步就立刻% MOD;两个 级别的余数相乘最高可达 ,超出int上限()整整五亿倍,乘法算式最左端必写1LL *或全程使用long long!- 【减法必套
+ MOD护盾,除法严禁直接拆模】:凡是模意义下出现减号-,肌肉记忆立刻套上((A - B) % MOD + MOD) % MOD;凡是算式中出现除号/,在没有学乘法逆元前,绝对禁止对分子取模后再除,必须在取模前先把分母整除约掉!
🔍 二、 具象代码与数据推演(有举例)
示例:含负权数组的前缀和同余作差与除二陷阱对比
我们取小模数 MOD = 7,对数组 a[1..4] = {5, 6, -3, 10} 维护模 7 意义下的前缀和数组 pre[],随后演示查询子区间 [2, 4] 的元素和(真实和为 ,对 7 取模真实答案应为 6),并对比“取模后直接除以 2”的错误现场:
#include <iostream>
using namespace std;
const int MOD = 7;
int main() {
int a[5] = {0, 5, 6, -3, 10}; // 下标 1~4,真实前缀和依次为 5, 11, 8, 18
int pre[5] = {0};
for (int i = 1; i <= 4; i++) {
int val = (a[i] % MOD + MOD) % MOD; // 将可能为负的元素安全归入 [0, 6]
pre[i] = (pre[i - 1] + val) % MOD; // 边加边取模
cout << "i=" << i << ": val=" << val << ", pre=" << pre[i] << endl;
}
// 查询子区间 [2, 4] 的和(真实和 6 - 3 + 10 = 13,对 7 取模应得 6)
int bad_sub = (pre[4] - pre[1]) % MOD; // 陷阱1:(4 - 5) % 7 = -1
int ok_sub = ((pre[4] - pre[1]) % MOD + MOD) % MOD;// 正确:(-1 + 7) % 7 = 6
cout << "sub [2,4]: bad=" << bad_sub << ", ok=" << ok_sub << endl;
// 计算前 3 项真实和(5 + 6 - 3 = 8)除以 2 后对 7 取模(真实值 8 / 2 = 4)
int bad_div = pre[3] / 2; // 陷阱2:直接拿余数 1 / 2 = 0
int ok_div = ((a[1] + a[2] + a[3]) / 2) % MOD; // 正确:取模前先整除 8 / 2 = 4
cout << "div2 [1,3]: bad=" << bad_div << ", ok=" << ok_div << endl;
return 0;
}分步内存变量变化与同余推演表
| 执行阶段 | 真实未取模数值 | 归一化 val 计算 |
模 7 存储值 pre[i] |
关键观察与底层现象剖析 |
|---|---|---|---|---|
i = 1 (a[1] = 5) |
真实和 5 |
(5 % 7 + 7) % 7 = 5 |
5 |
正数余数保持 5 |
i = 2 (a[2] = 6) |
真实和 11 |
(6 % 7 + 7) % 7 = 6 |
(5 + 6) % 7 = 4 |
满 7 绕环归零,余数从 5 回落到 4 |
i = 3 (a[3] = -3) |
真实和 8 |
(-3 % 7 + 7) % 7 = 4 |
(4 + 4) % 7 = 1 |
加上 -3 等价于模 7 下加上 +4,8 % 7 = 1 |
i = 4 (a[4] = 10) |
真实和 18 |
(10 % 7 + 7) % 7 = 3 |
(1 + 3) % 7 = 4 |
18 = 2 * 7 + 4,余数为 4 |
区间作差 [2, 4] |
18 - 5 = 13 |
pre[4] - pre[1] = 4 - 5 = -1 |
bad = -1 / ok = 6 |
尽管 18 > 5,但余数 4 < 5!不加 MOD 必得 -1 |
除 2 取模 [1, 3] |
8 / 2 = 4 |
pre[3] 仅存余数 1 |
bad = 0 / ok = 4 |
8 取模后丢失了 1 * 7,奇数余数 1 / 2 惨变 0 |
程序标准输出:
i=1: val=5, pre=5
i=2: val=6, pre=4
i=3: val=4, pre=1
i=4: val=3, pre=4
sub [2,4]: bad=-1, ok=6
div2 [1,3]: bad=0, ok=4⚡ 三、 考场高频避坑指南(正误辨析)
在 GESP 五级真题与 CSP-J 赛场上,以下三大隐蔽雷区每年都会吞掉大批考生的本该到手的分数:
❌ 易错点 1:误以为“溢出也是某种取模,最后再 % 1000000007 结果一样”!
- 错误代码:求 对 取模时,写
unsigned long long ans = 1; for (int i = 1; i <= n; i++) ans *= i; cout << ans % 1000000007;。 - 为什么错:无符号 64 位整数自然溢出,本质上是硬件自动对 取了模(而有符号整数溢出在 C++ 中更是直接触发未定义行为 UB)!由于 并不是 的整数倍,一个数先对 取模丢失高位后,它除以 的余数已经彻底面目全非(好比先对
10取模把17变成了7,再对6取模得1,而真实的17 % 6明明是5)! - 正确规范:必须在循环内部每乘一次就立刻对目标模数取模:
ans = (ans * i) % MOD;。
❌ 易错点 2:对已经取过模的变量直接用 <、> 或 max() 比较大小!
- 错误操作:在求最大路径权值和并要求答案对 取模的动态规划题中,边转移边取模:
dp[i] = max(dp[i - 1], dp[i - 2] + a[i]) % MOD;。 - 为什么错:同余关系只保持加、减、乘,绝对不保持大小顺序(序关系)! 例如路径 A 的真实总和是 (取模后余数为
1),路径 B 的真实总和是 (取模后余数为500)。明明路径 A 远大于路径 B,取模后再调max(1, 500)却挑中了较小的路径 B,后续所有状态全盘崩塌! - 正确规范:凡是既要“求最大值/最小值”又要“对结果取模”的题目,如果总和在
long long范围内(如 ),必须在整个 DP 过程中存真实值比较大小,仅在最终输出时取模;若真实值连long long都装不下,则通常需要改用对数转换或高精度,绝不能边取模边max!
❌ 易错点 3:简写 (a - b + MOD) % MOD 时未确认 a, b 范围,依然算出负数!
- 错误认知:死记硬背“减法取模就是加一个
MOD”,遇到任意两个long long变量a, b直接写(a - b + MOD) % MOD。 - 为什么错:单加一个
+ MOD能把结果拉回正数的前提是a和b都已经提前取过模,严格落在[0, MOD - 1]内(此时a - b >= -(MOD - 1),加上一个MOD后必有a - b + MOD >= 1 > 0)。如果b是一个尚未取模的原始大数(例如a = 5, b = 30, MOD = 7),那么a - b + MOD = 5 - 30 + 7 = -18,对7取模得到-4,照样是负数! - 正确规范:不确定操作数是否已归入
[0, MOD - 1]时,老老实实先做% MOD把差值缩进(-MOD, MOD),再加MOD取模:((a - b) % MOD + MOD) % MOD,万无一失!
📝 四、 真题实战演练与精析(有例题:3 道)
【例题 1 · 单选题】(GESP 五级 / CSP-J 初赛阅读程序:负数取模与除法拆模输出预测)
题目:阅读以下严格遵循 C++11 标准的程序片段,其运行后的标准输出结果是( )
#include <iostream>
using namespace std;
int main() {
const int MOD = 7;
int a = -10 % MOD;
int b = (-10 % MOD + MOD) % MOD;
int pre_r = 2, pre_l = 6;
int c = ((pre_r - pre_l) % MOD + MOD) % MOD;
int d = ((12 % MOD) / (3 % MOD)) % MOD;
cout << a << " " << b << " " << c << " " << d << endl;
return 0;
}- A.
4 4 3 4 - B.
-3 4 -4 1 - C.
-3 4 3 4 - D.
-3 4 3 1
🔍 答案与逐项排除解析:
- 正确答案:D
- 解析过程:
- 求
a:C++11 中-10 / 7向零截断得-1,故a = -10 - (-1) * 7 = -3(排除把 C++%当成数学正余数的 A); - 求
b:在a = -3的基础上加上7得4,4 % 7 = 4,成功将负余数扶正为最小非负余数4; - 求
c:pre_r - pre_l = 2 - 6 = -4,(-4 % 7 + 7) % 7 = (-4 + 7) % 7 = 3(排除未理解+ MOD扶正作用的 B); - 求
d:切忌按数学真实值(12 / 3) % 7 = 4作答!代码实际执行的是先取模再整除:12 % 7 = 5,3 % 7 = 3,随后整数除法5 / 3 = 1(小数部分截断丢弃),最后1 % 7 = 1(排除误以为除法满足取模分配律的 C,锁定 D)!
- 求
【例题 2 · 判断题】(GESP 五级数论概念辨析:同余乘法消去律的隐藏前提)
题目:设 为任意正整数,()为正整数模数。如果满足同余式 ,且 不是 的整数倍(即 ),那么一定可以两边同时约去 ,推出 。( )
🔍 答案与反例证明:
- 结论:错误(×)
- 辨析证明:
- 在普通实数等式中,只要 ,由 就能直接约去 得 ;但在模 同余式中, 远远不够,两边能直接约去 的充要条件是 与模数 互质,即 !
- 极简反例:取 。
- 检验前提: 显然不是 的倍数();左边 ,右边 ,由于 能被 整除,确实满足 ;
- 检验结论:约去 后, 而 ,显然 !
- 数论本质:。当 时, 自己替 分担了因子 ,此时只能推出 (上例中 ,即模
3同余)。这也是为什么除法在模合数或未互质时极其危险的根本原因!
【例题 3 · 微代码实战】(GESP 五级 / CSP-J 复赛综合实战:模意义下的区间能量倍增统计)
题目描述:给定一个长度为 ()的整数序列 (注意元素可能为负,),以及 ()次查询。每次查询给定三个正整数 (,):
设子区间 的元素总和为 ,倍增系数为前 个正整数之和 。请计算每次查询的区间总能量 对 1000000007 取模后的最小非负余数(即输出范围必须在 内)。
输入格式: 第一行包含两个正整数 和 ,分别表示序列长度与查询次数。 第二行包含 个整数 。 接下来 行,每行包含三个正整数 ,描述一次查询。
输出格式: 输出共 行,每行一个 范围内的整数,表示对应查询的答案。
💡 算法建模与四大取模铁律全覆盖要点:
- 负数读入归一化与加法取模: 可达 ,预处理前缀和时先用
(x % MOD + MOD) % MOD映射到 ,再累加取模; - 前缀和作差防负护盾:区间和余数必须写
((pre[r] - pre[l - 1]) % MOD + MOD) % MOD,严防pre[r] < pre[l - 1]时吐出负余数; - 超大 等差求和破除“溢出 + 除法禁模”双重死局: 高达 ,若先算
k * (k + 1)会瞬间撑爆long long();若先对k取模再除以2又违背除法不可直接取模铁律!正确解法是利用相邻两整数 与 必有一偶的性质,在取模前先挑出那个偶数整除2,化为纯乘法后再各自% MOD相乘!
#include <iostream>
using namespace std;
const int MAXN = 100005;
const long long MOD = 1000000007;
long long pre[MAXN];
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
// 1. 负数或大整数统一归一化至 [0, MOD - 1],再做前缀累加取模
long long val = (x % MOD + MOD) % MOD;
pre[i] = (pre[i - 1] + val) % MOD;
}
while (q--) {
int l, r;
long long k;
cin >> l >> r >> k;
// 2. 前缀和同余作差:pre[r] 可能小于 pre[l - 1],必须 +MOD 防负余数
long long range_sum = ((pre[r] - pre[l - 1]) % MOD + MOD) % MOD;
// 3. 计算 k * (k + 1) / 2 mod MOD:相邻整数必有一偶,取模前先对偶数整除 2
long long u = k, v = k + 1;
if (u % 2 == 0) {
u /= 2;
} else {
v /= 2;
}
long long factor = ((u % MOD) * (v % MOD)) % MOD;
// 4. 64 位乘法取模防爆 int
long long ans = (range_sum * factor) % MOD;
cout << ans << endl;
}
return 0;
}- 输入样例:
Code4 行
4 2 1000000005 10 -3 2 1 2 2 2 4 3 - 输出样例:
(样例解释:第 1 次查询区间Code2 行
24 54[1, 2]真实和为1000000005 + 10 = 1000000015,模1000000007余数为8,系数2 * 3 / 2 = 3,乘积为8 * 3 = 24;第 2 次查询区间[2, 4]真实和为10 + (-3) + 2 = 9,尽管前缀和余数pre[4] = 7小于pre[1] = 1000000005,但经+ MOD修正后精准还原为9,乘以系数3 * 4 / 2 = 6得54。)
所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP/CSP考点精讲】GESP四级/五级 / CSP-J 必背:递推 vs 递归——如何手画“递归调用树”秒杀初赛阅读程序题?
为什么在考场上遇到一句看似简单的 return f(n - 1) + f(n - 2);,有些同学在脑子里绕了三层就彻底“死机”,完全算不清函数到底被调用了多少次?为什么仅仅把 cout << n; 放在递归调用语句的前面和后面,打印出来的数字顺序就会发生天翻地覆的“逆...
【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:从 O(2^n) 到 O(n) 的奇迹——重叠子问题与记忆化搜索
为什么一段只有 5 行的斐波那契递归代码 return fib(n - 1) + fib(n - 2);,当输入 n = 10 时瞬间出解,一旦输入 n = 45 就会触发超过 22 亿次函数调用,把评测机死死卡在 TLE(运行超时)?更神奇的是,为什么在不改变递归主体...
【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:分治思想与归并排序(Merge Sort)——顺手秒杀“逆序对”统计
当题目给出的数据规模从 n = 1000 跃升到 n = 10^5 时,无论是冒泡排序、直接插入排序,还是用双重 for 循环暴力枚举统计“逆序对”,运算次数都会瞬间飙升至 (n(n-1)/2) ≈ 5 × 10^9 次,在 1 秒时限面前毫无悬念地触发 TLE(运行超...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

