OneCoder Avatar
OneCodercoderli.com · 1024 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:同余定理与取模铁律——为什么减法取模要先 +MOD,而除法绝对不能直接取模?

📅 2026-11-18·✍️ OneCoder·计算中...·⏱️ 30 分钟

在信奥赛场上,几乎每一道递推计数、动态规划或数论求值题的末尾都会印着那句熟悉的提示:“由于答案可能很大,请输出答案对 (即 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 初赛/复赛必考

在考场实战与初赛阅读程序题中,考生最容易在以下三大痛点上丢分:

  1. “攒到最后才取模,中途早已溢出变质”:误以为同余只管最终结果,在连乘或递推中途不取模,或者两个 int 变量做 (a * b) % MOD 时漏写 1LL * 强制类型提升,导致乘积在进入 % 运算前就已经在 32 位寄存器里溢出截断,神仙难救;
  2. “混淆数学最小非负余数与 C++ 负数取模,减法算出一堆负值”:当两个取过模的数相减(例如前缀和 pre[r] - pre[l - 1])时,即使原区间和明明是正数,取模后的 pre[r] 也完全可能小于 pre[l - 1],直接 % MOD 会保留负号输出负数;
  3. “把四则运算一视同仁,对着除法强行套用取模分配律”:看到加、减、乘都能拆开各自 % MOD,便想当然地认为 (a / b) % MOD 等于 ((a % MOD) / (b % MOD)) % MOD,在涉及除以 2、除以阶乘的公式里全盘算错!

🧠 一、 核心原理深度拆解(有理论)

1. 同余关系的本质:“余数时钟环”与等价类

给定一个正整数模数 (),如果两个整数 和 除以 所得的最小非负余数完全相同(或者等价地说,它们的差 能够被 整除,记作 ),我们就称 与 模 同余,记作:

我们可以把模 的世界想象成一座只有 0, 1, 2, ..., m - 1 共 个刻度的环形时钟(以 的星期时钟为例):

Code12 行
================================================================================
【模 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 相乘

💡 考场黄金法则(背诵直接套用):

  1. 【加乘边算边模,1LL 护航防爆】:只要题目要求对 MOD(如 )取模,加法和乘法必须每算一步就立刻 % MOD;两个 级别的余数相乘最高可达 ,超出 int 上限()整整五亿倍,乘法算式最左端必写 1LL * 或全程使用 long long!
  2. 【减法必套 + MOD 护盾,除法严禁直接拆模】:凡是模意义下出现减号 -,肌肉记忆立刻套上 ((A - B) % MOD + MOD) % MOD;凡是算式中出现除号 /,在没有学乘法逆元前,绝对禁止对分子取模后再除,必须在取模前先把分母整除约掉!

🔍 二、 具象代码与数据推演(有举例)

示例:含负权数组的前缀和同余作差与除二陷阱对比

我们取小模数 MOD = 7,对数组 a[1..4] = {5, 6, -3, 10} 维护模 7 意义下的前缀和数组 pre[],随后演示查询子区间 [2, 4] 的元素和(真实和为 ,对 7 取模真实答案应为 6),并对比“取模后直接除以 2”的错误现场:

C++25 行
#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

程序标准输出:

Code6 行
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 标准的程序片段,其运行后的标准输出结果是( )

C++13 行
#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
  • 解析过程:
    1. 求 a:C++11 中 -10 / 7 向零截断得 -1,故 a = -10 - (-1) * 7 = -3(排除把 C++ % 当成数学正余数的 A);
    2. 求 b:在 a = -3 的基础上加上 7 得 4,4 % 7 = 4,成功将负余数扶正为最小非负余数 4;
    3. 求 c:pre_r - pre_l = 2 - 6 = -4,(-4 % 7 + 7) % 7 = (-4 + 7) % 7 = 3(排除未理解 + MOD 扶正作用的 B);
    4. 求 d:切忌按数学真实值 (12 / 3) % 7 = 4 作答!代码实际执行的是先取模再整除:12 % 7 = 5,3 % 7 = 3,随后整数除法 5 / 3 = 1(小数部分截断丢弃),最后 1 % 7 = 1(排除误以为除法满足取模分配律的 C,锁定 D)!

【例题 2 · 判断题】(GESP 五级数论概念辨析:同余乘法消去律的隐藏前提)

题目:设 为任意正整数,()为正整数模数。如果满足同余式 ,且 不是 的整数倍(即 ),那么一定可以两边同时约去 ,推出 。( )

🔍 答案与反例证明:

  • 结论:错误(×)
  • 辨析证明:
    1. 在普通实数等式中,只要 ,由 就能直接约去 得 ;但在模 同余式中, 远远不够,两边能直接约去 的充要条件是 与模数 互质,即 !
    2. 极简反例:取 。
      • 检验前提: 显然不是 的倍数();左边 ,右边 ,由于 能被 整除,确实满足 ;
      • 检验结论:约去 后, 而 ,显然 !
    3. 数论本质:。当 时, 自己替 分担了因子 ,此时只能推出 (上例中 ,即模 3 同余)。这也是为什么除法在模合数或未互质时极其危险的根本原因!

【例题 3 · 微代码实战】(GESP 五级 / CSP-J 复赛综合实战:模意义下的区间能量倍增统计)

题目描述:给定一个长度为 ()的整数序列 (注意元素可能为负,),以及 ()次查询。每次查询给定三个正整数 (,): 设子区间 的元素总和为 ,倍增系数为前 个正整数之和 。请计算每次查询的区间总能量 对 1000000007 取模后的最小非负余数(即输出范围必须在 内)。

输入格式: 第一行包含两个正整数 和 ,分别表示序列长度与查询次数。 第二行包含 个整数 。 接下来 行,每行包含三个正整数 ,描述一次查询。

输出格式: 输出共 行,每行一个 范围内的整数,表示对应查询的答案。

💡 算法建模与四大取模铁律全覆盖要点:

  1. 负数读入归一化与加法取模: 可达 ,预处理前缀和时先用 (x % MOD + MOD) % MOD 映射到 ,再累加取模;
  2. 前缀和作差防负护盾:区间和余数必须写 ((pre[r] - pre[l - 1]) % MOD + MOD) % MOD,严防 pre[r] < pre[l - 1] 时吐出负余数;
  3. 超大 等差求和破除“溢出 + 除法禁模”双重死局: 高达 ,若先算 k * (k + 1) 会瞬间撑爆 long long();若先对 k 取模再除以 2 又违背除法不可直接取模铁律!正确解法是利用相邻两整数 与 必有一偶的性质,在取模前先挑出那个偶数整除 2,化为纯乘法后再各自 % MOD 相乘!
C++42 行
#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
  • 输出样例:
    Code2 行
    24
    54
    (样例解释:第 1 次查询区间 [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。)
看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

GESP 编程与算法 · 五级⏱️ 26 分钟

【GESP/CSP考点精讲】GESP四级/五级 / CSP-J 必背:递推 vs 递归——如何手画“递归调用树”秒杀初赛阅读程序题?

为什么在考场上遇到一句看似简单的 return f(n - 1) + f(n - 2);,有些同学在脑子里绕了三层就彻底“死机”,完全算不清函数到底被调用了多少次?为什么仅仅把 cout << n; 放在递归调用语句的前面和后面,打印出来的数字顺序就会发生天翻地覆的“逆...

阅读全文 →
GESP 编程与算法 · 五级⏱️ 31 分钟

【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 编程与算法 · 五级⏱️ 33 分钟

【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:分治思想与归并排序(Merge Sort)——顺手秒杀“逆序对”统计

当题目给出的数据规模从 n = 1000 跃升到 n = 10^5 时,无论是冒泡排序、直接插入排序,还是用双重 for 循环暴力枚举统计“逆序对”,运算次数都会瞬间飙升至 (n(n-1)/2) ≈ 5 × 10^9 次,在 1 秒时限面前毫无悬念地触发 TLE(运行超...

阅读全文 →
OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!