同余定理与取模运算铁律

同余定理与取模运算铁律

在信奥赛场上,几乎每一道递推计数、动态规划或数论求值题的末尾都会印着那句熟悉的提示:“由于答案可能很大,请输出答案对 109+710^9 + 7(即 1000000007)取模后的结果。” 许多同学看到这句话暗自窃喜,以为只要在 cout 输出前顺手补一个 % MOD 就万事大吉;殊不知评测结果出来却是一片刺眼的 WA(答案错误):有人在循环里一路累加累乘,没等走到输出语句就已经撑爆 long long 溢出回绕;有人在前缀和作差时写了 (pre[r] - pre[l - 1]) % MOD,莫名其妙吐出一串负数;更有人在计算组合数或等差求和公式 n(n+1)2\frac{n(n+1)}{2} 时,天真地写下 ((n % MOD) * ((n + 1) % MOD) / 2) % MOD,掉进了“除法直接取模”的致命深渊!在 GESP 五级认证以及 CSP-J/S 初赛与复赛中,同余关系 a≡b(modm)a \equiv b \pmod m 的代数性质、加减乘“边算边模”防溢出公式、C++ 负数取模向零截断机制与 + MOD 扶正铁律,以及除法不满足取模分配律的破局之道,是决定计数与数论题能否稳拿满分的基本功。本文将带你从底层数学与编译器行为出发,把取模运算的所有暗礁一次性彻底扫清。

🎯 考纲锚点与核心痛点

📍 对应考点:深入理解初等数论中的同余概念 a≡b(modm)a \equiv b \pmod m 及其基本性质,熟练掌握模意义下加法、减法与乘法的同余保持律与防溢出编码规范,厘清 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. 同余关系的本质:“余数时钟环”与等价类

给定一个正整数模数 mm(m≥2m \ge 2),如果两个整数 aa 和 bb 除以 mm 所得的最小非负余数完全相同(或者等价地说,它们的差 a−ba - b 能够被 mm 整除,记作 m∣(a−b)m \mid (a - b)),我们就称 aa 与 bb 模 mm 同余,记作:

a≡b(modm)a \equiv b \pmod m

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

================================================================================
【模 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)
================================================================================

同余关系天生具备与等号 = 极为相似的三大等价性质:自反性(a≡a(modm)a \equiv a \pmod m)、对称性(若 a≡ba \equiv b 则 b≡ab \equiv a)和传递性(若 a≡ba \equiv b 且 b≡cb \equiv c,则 a≡c(modm)a \equiv c \pmod m)。


2. 四则运算同余铁律:为什么加减乘都能拆,唯独除法绝对不行?

设整数 a=k1m+r1a = k_1 m + r_1,b=k2m+r2b = k_2 m + r_2(其中 r1=a mod mr_1 = a \bmod m,r2=b mod mr_2 = b \bmod m)。我们用最直观的代数展开来看看四则运算在模 mm 下会发生什么:

  • 加法同余律(成立 ✅):

    a+b=(k1+k2)m+(r1+r2)  ⟹  (a+b) mod m=(r1+r2) mod ma + b = (k_1 + k_2)m + (r_1 + r_2) \implies (a + b) \bmod m = (r_1 + r_2) \bmod m

    整倍数的 (k1+k2)m(k_1 + k_2)m 在除以 mm 时直接化为 0 消去!

  • 减法同余律(数学成立,代码需防负 ✅):

    a−b=(k1−k2)m+(r1−r2)  ⟹  a−b≡r1−r2(modm)a - b = (k_1 - k_2)m + (r_1 - r_2) \implies a - b \equiv r_1 - r_2 \pmod m
  • 乘法同余律(成立 ✅):

    a×b=(k1k2m+k1r2+k2r1)⋅m+r1r2  ⟹  (a×b) mod m=(r1×r2) mod ma \times b = (k_1 k_2 m + k_1 r_2 + k_2 r_1)\cdot m + r_1 r_2 \implies (a \times b) \bmod m = (r_1 \times r_2) \bmod m

    展开式中前三项全都带有因子 mm,对 mm 取模瞬间灰飞烟灭,只剩余数之积 r1r2r_1 r_2!这就是为什么成千上万步的加法和乘法,每一步都可以放心地把大数直接替换成它的余数(“边算边取模”),而最终余数丝毫不差!

  • 除法同余分配律(绝对不成立 ❌): 为什么除法会彻底失效?请看一个一秒击碎幻想的反例:设 a=12,b=3,m=5a = 12, b = 3, m = 5。

    • 真实结果:先做整除 12÷3=412 \div 3 = 4,再对 55 取模得 4 mod 5=44 \bmod 5 = \mathbf{4};
    • 错误拆模:若先对分子分母分别取模,12 mod 5=212 \bmod 5 = 2,3 mod 5=33 \bmod 5 = 3,相除变成 2÷3=02 \div 3 = \mathbf{0}(整数除法截断)!4 瞬间变成了 0!
    • 底层根源:在 a=k1m+r1a = k_1 m + r_1 中,当你除以 bb 时,k1mb\frac{k_1 m}{b} 不一定是 mm 的整数倍(因为 bb 可能会把模数 mm 旁边的系数 k1k_1 约掉一部分,改变除以 mm 的余数)!
    • 考场破局正道:在 GESP 五级与 CSP-J 阶段(未涉及费马小定理与乘法逆元时),遇到模意义下的除法(如 n(n+1)2 mod m\frac{n(n+1)}{2} \bmod m 或小组合数),必须在取模之前利用因数整除性质先把分母彻底约掉,化为纯乘法后再取模!

3. C++ 负数取模陷阱与四则安全取模标准速查表

在数论定义中,任何整数除以正整数 mm 的余数都规定落在非负区间 [0,m−1][0, m - 1] 内(例如 −10=(−2)×7+4-10 = (-2) \times 7 + 4,数学余数为 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++ 余数统一拉回标准非负区间 [0,m−1][0, m - 1]?只需在时钟环上顺时针拨一圈(+ m),再对 m 取一次模防止原本就是正数时越界(例如 (4 + 7) % 7 = 4,(-3 + 7) % 7 = 4)!由此得到全场景通用的四则取模标准范式表:

运算场景数学目标(结果归入 [0,M−1][0, M-1])错误高危写法(考场重灾区)C++11 满分安全写法(设 M = MOD)
单数归一化a mod Ma \bmod M(aa 可能为负)a % M(a<0a < 0 时得负数)(a % M + M) % M
模加法(a+b) mod M(a + b) \bmod M(a + b) % M(a+b 可能爆 int)((a % M) + (b % M)) % M(推荐 long long)
模减法(a−b) mod M(a - b) \bmod M(a - b) % M(余数相减极易为负)((a - b) % M + M) % M
模乘法(a×b) mod M(a \times b) \bmod M(a * b) % M(两 int 相乘先溢出)(1LL * (a % M) * (b % M)) % M
含除整式k(k+1)2 mod M\frac{k(k+1)}{2} \bmod M((k % M) * ((k+1) % M) / 2) % M先挑 k,k+1k, k+1 中的偶数 / 2,再各自 % M 相乘

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

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

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

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

我们取小模数 MOD = 7,对数组 a[1..4] = {5, 6, -3, 10} 维护模 7 意义下的前缀和数组 pre[],随后演示查询子区间 [2, 4] 的元素和(真实和为 6+(−3)+10=136 + (-3) + 10 = 13,对 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 = 55正数余数保持 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 = 418 = 2 * 7 + 4,余数为 4
区间作差 [2, 4]18 - 5 = 13pre[4] - pre[1] = 4 - 5 = -1bad = -1 / ok = 6尽管 18 > 5,但余数 4 < 5!不加 MOD 必得 -1
除 2 取模 [1, 3]8 / 2 = 4pre[3] 仅存余数 1bad = 0 / ok = 48 取模后丢失了 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 结果一样”!

  • 错误代码:求 n!n! 对 p=109+7p = 10^9 + 7 取模时,写 unsigned long long ans = 1; for (int i = 1; i <= n; i++) ans *= i; cout << ans % 1000000007;。
  • 为什么错:无符号 64 位整数自然溢出,本质上是硬件自动对 M1=264M_1 = 2^{64} 取了模(而有符号整数溢出在 C++ 中更是直接触发未定义行为 UB)!由于 2642^{64} 并不是 109+710^9 + 7 的整数倍,一个数先对 2642^{64} 取模丢失高位后,它除以 109+710^9 + 7 的余数已经彻底面目全非(好比先对 10 取模把 17 变成了 7,再对 6 取模得 1,而真实的 17 % 6 明明是 5)!
  • 正确规范:必须在循环内部每乘一次就立刻对目标模数取模:ans = (ans * i) % MOD;。

❌ 易错点 2:对已经取过模的变量直接用 <、> 或 max() 比较大小!

  • 错误操作:在求最大路径权值和并要求答案对 109+710^9 + 7 取模的动态规划题中,边转移边取模:dp[i] = max(dp[i - 1], dp[i - 2] + a[i]) % MOD;。
  • 为什么错:同余关系只保持加、减、乘,绝对不保持大小顺序(序关系)! 例如路径 A 的真实总和是 109+810^9 + 8(取模后余数为 1),路径 B 的真实总和是 500500(取模后余数为 500)。明明路径 A 远大于路径 B,取模后再调 max(1, 500) 却挑中了较小的路径 B,后续所有状态全盘崩塌!
  • 正确规范:凡是既要“求最大值/最小值”又要“对结果取模”的题目,如果总和在 long long 范围内(如 ≤1018\le 10^{18}),必须在整个 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
  • 解析过程:
    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 五级数论概念辨析:同余乘法消去律的隐藏前提)

题目:设 a,b,ca, b, c 为任意正整数,mm(m≥2m \ge 2)为正整数模数。如果满足同余式 a×c≡b×c(modm)a \times c \equiv b \times c \pmod m,且 cc 不是 mm 的整数倍(即 c≢0(modm)c \not\equiv 0 \pmod m),那么一定可以两边同时约去 cc,推出 a≡b(modm)a \equiv b \pmod m。( )

🔍 答案与反例证明:

  • 结论:错误(×)
  • 辨析证明:
    1. 在普通实数等式中,只要 c≠0c \neq 0,由 ac=bcac = bc 就能直接约去 cc 得 a=ba = b;但在模 mm 同余式中,c≢0(modm)c \not\equiv 0 \pmod m 远远不够,两边能直接约去 cc 的充要条件是 cc 与模数 mm 互质,即 gcd⁡(c,m)=1\gcd(c, m) = 1!
    2. 极简反例:取 a=1,b=4,c=2,m=6a = 1, b = 4, c = 2, m = 6。
      • 检验前提:c=2c = 2 显然不是 66 的倍数(2≢0(mod6)2 \not\equiv 0 \pmod 6);左边 a×c=1×2=2a \times c = 1 \times 2 = 2,右边 b×c=4×2=8b \times c = 4 \times 2 = 8,由于 8−2=68 - 2 = 6 能被 66 整除,确实满足 2≡8(mod6)2 \equiv 8 \pmod 6;
      • 检验结论:约去 c=2c = 2 后,a=1a = 1 而 b=4b = 4,显然 1≢4(mod6)1 \not\equiv 4 \pmod 6!
    3. 数论本质:ac≡bc(modm)  ⟺  m∣c(a−b)ac \equiv bc \pmod m \iff m \mid c(a - b)。当 gcd⁡(c,m)=d>1\gcd(c, m) = d > 1 时,cc 自己替 (a−b)(a - b) 分担了因子 dd,此时只能推出 a≡b(modmgcd⁡(c,m))a \equiv b \pmod{\frac{m}{\gcd(c, m)}}(上例中 1≡4(mod6/2)1 \equiv 4 \pmod{6 / 2},即模 3 同余)。这也是为什么除法在模合数或未互质时极其危险的根本原因!

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

题目描述:给定一个长度为 nn(1≤n≤1051 \le n \le 10^5)的整数序列 a1,a2,…,ana_1, a_2, \dots, a_n(注意元素可能为负,−109≤ai≤109-10^9 \le a_i \le 10^9),以及 qq(1≤q≤1051 \le q \le 10^5)次查询。每次查询给定三个正整数 l,r,kl, r, k(1≤l≤r≤n1 \le l \le r \le n,1≤k≤10181 \le k \le 10^{18}): 设子区间 [l,r][l, r] 的元素总和为 S=∑i=lraiS = \sum_{i=l}^{r} a_i,倍增系数为前 kk 个正整数之和 C=1+2+⋯+k=k(k+1)2C = 1 + 2 + \dots + k = \frac{k(k + 1)}{2}。请计算每次查询的区间总能量 (S×C)(S \times C) 对 1000000007 取模后的最小非负余数(即输出范围必须在 [0,1000000006][0, 1000000006] 内)。

输入格式: 第一行包含两个正整数 nn 和 qq,分别表示序列长度与查询次数。 第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n。 接下来 qq 行,每行包含三个正整数 l,r,kl, r, k,描述一次查询。

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

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

  1. 负数读入归一化与加法取模:aia_i 可达 −109-10^9,预处理前缀和时先用 (x % MOD + MOD) % MOD 映射到 [0,MOD−1][0, \text{MOD}-1],再累加取模;
  2. 前缀和作差防负护盾:区间和余数必须写 ((pre[r] - pre[l - 1]) % MOD + MOD) % MOD,严防 pre[r] < pre[l - 1] 时吐出负余数;
  3. 超大 kk 等差求和破除“溢出 + 除法禁模”双重死局:kk 高达 101810^{18},若先算 k * (k + 1) 会瞬间撑爆 long long(103610^{36});若先对 k 取模再除以 2 又违背除法不可直接取模铁律!正确解法是利用相邻两整数 kk 与 k+1k + 1 必有一偶的性质,在取模前先挑出那个偶数整除 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;
}
  • 输入样例:
    4 2
    1000000005 10 -3 2
    1 2 2
    2 4 3
  • 输出样例:
    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。)

本文由coderli.com原创,按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github:https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群: 688906745

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于