1. 项目概述从一道经典数论题说起最近在带学生刷信奥信息学奥林匹克题目时又遇到了P2261 [CQOI2007] 余数求和这道题。这道题可以说是数论分块整除分块的入门级经典例题几乎每个认真准备信奥C竞赛的同学都会在某个阶段遇到它。题目本身描述很简单给定两个正整数n和k要求计算∑_{i1}^{n} (k mod i)的值。这里的mod就是取余运算。乍一看这不就是一个简单的循环累加吗从1到n遍历把k % i的结果加起来不就行了很多初学者确实会这么想然后信心满满地写下一个for循环。但只要你把样例或者稍微大一点的数字比如n和k都是10^9级别代入程序就会立刻超时给你一个无情的TLE时间超限。这正是这道题的“陷阱”和价值所在——它逼着你不能使用朴素的O(n)算法必须去寻找数学规律用O(√k)甚至更优的复杂度来解决。这恰恰是信奥竞赛考察的核心能力之一将实际问题抽象为数学模型并利用数学知识进行优化。今天我就结合自己多年的刷题和教学经验带你彻底拆解这道题不仅给出C实现代码更重要的是讲清楚背后的数学原理数论分块、推导过程、代码细节以及那些容易踩坑的地方。2. 核心思路拆解化“余”为“和”的数学魔法2.1 为什么暴力循环行不通我们首先来量化一下暴力方法的问题。题目中n和k的范围虽然没有在标题中明确给出但在原题中通常上限可以达到10^9。一个从1到10^9的循环即使在当今最快的个人计算机上也需要数秒甚至更长时间才能跑完而信奥竞赛题目的时间限制通常是1秒或2秒。在1秒内C大约能执行10^8量级的基本操作。10^9的循环远远超出了这个限制因此暴力法必然超时。这就要求我们必须找到一个时间复杂度远低于O(n)的算法。2.2 关键数学变换余数公式的展开解决这道题的第一步也是最关键的一步是利用取余运算的定义进行公式变换。取余运算k mod i的定义是k mod i k - i * ⌊k/i⌋。其中⌊k/i⌋表示对k/i的结果向下取整在C中就是整数除法k / i的结果当k和i都是整数时。于是我们要求和的式子就可以进行如下变换G(n, k) ∑_{i1}^{n} (k mod i) ∑_{i1}^{n} (k - i * ⌊k/i⌋)这个求和可以拆开G(n, k) ∑_{i1}^{n} k - ∑_{i1}^{n} (i * ⌊k/i⌋)第一部分∑_{i1}^{n} k就是n个k相加等于n * k。 所以原问题转化为G(n, k) n * k - ∑_{i1}^{n} (i * ⌊k/i⌋)现在问题的核心变成了如何高效计算∑_{i1}^{n} (i * ⌊k/i⌋)。暴力计算它依然是O(n)的。观察⌊k/i⌋这个式子当i变化时它的值并不是每次都在变。例如当k10时i1,⌊10/1⌋10i2,⌊10/2⌋5i3,⌊10/3⌋3i4,⌊10/4⌋2i5,⌊10/5⌋2i6,⌊10/6⌋1i7,⌊10/7⌋1i8,⌊10/8⌋1i9,⌊10/9⌋1i10,⌊10/10⌋1你会发现从i4到i5⌊k/i⌋的值都是2从i6到i10值都是1。这些值相同的i构成了一个连续的整数区间。数论分块整除分块要做的就是快速找到这些区间然后对每个区间进行整体计算从而将复杂度从O(n)降低到O(√k)。2.3 数论分块整除分块原理详解数论分块的核心是这样一个结论对于给定的正整数k和i使得⌊k/i⌋ qq是一个常数的i的取值构成一个连续的区间[l, r]。并且这个区间的右端点r可以直接由左端点l和q计算出来r ⌊k / q⌋。但更常用的是另一个等价的公式r ⌊k / ⌊k/l⌋⌋。推导过程 设q ⌊k/l⌋即区间左端点l对应的整除值。 我们要找最大的r使得对于所有i ∈ [l, r]都有⌊k/i⌋ q。 由整除的定义可知⌊k/i⌋ q等价于q ≤ k/i q1。 将不等式k/i q1变形得到i k/(q1)。 将不等式q ≤ k/i变形得到i ≤ k/q。 因为i是整数所以i的上界是⌊k/q⌋。 同时为了满足i k/(q1)i的最小值至少是⌊k/(q1)⌋ 1。但我们已经从l开始所以这个区间的右端点就是⌊k/q⌋。 因此区间[l, r]为[l, ⌊k / ⌊k/l⌋⌋]。这个区间的长度r-l1可能很长尤其是当l比较小的时候。这样我们就不需要遍历区间内的每一个i而是可以直接计算这个区间对总和的贡献。区间[l, r]对∑ (i * ⌊k/i⌋)的贡献 在这个区间内⌊k/i⌋是常数q。 所以这个区间的贡献是q * ∑_{il}^{r} i。 等差数列求和公式∑_{il}^{r} i (l r) * (r - l 1) / 2。 因此区间贡献 q * (l r) * (r - l 1) / 2。算法流程初始化ans n * kl 1。当l n且l k时循环因为当l k时⌊k/l⌋ 0后续贡献为0可以提前结束 a. 计算当前区间的q ⌊k/l⌋。 b. 如果q 0则后面所有i的贡献都是0直接跳出循环。 c. 计算当前区间的右端点r min(n, ⌊k/q⌋)。这里需要和n取最小值因为i的上限是n。 d. 计算当前区间对∑ (i * ⌊k/i⌋)的贡献contrib q * (l r) * (r - l 1) / 2。 e. 从ans中减去这个贡献ans - contrib。 f. 将l更新为r 1处理下一个区间。循环结束后ans即为所求的G(n, k)。这个算法的时间复杂度是O(√k)。因为⌊k/i⌋的值大约只有2√k种当i ≤ √k时⌊k/i⌋有√k种取值当i √k时⌊k/i⌋ ≤ √k最多也有√k种取值所以循环次数是O(√k)级别的。注意在计算contrib时(l r) * (r - l 1)这个乘积可能非常大在n和k为10^9时可能会超过32位整数int的范围。因此我们必须使用64位整数在C中通常是long long来进行中间计算和存储最终结果否则会导致溢出得到错误答案。3. C代码实现与逐行解析理解了数学原理后我们来看具体的C代码实现。我会提供两个版本的代码一个是清晰易懂的基础版本另一个是考虑了边界情况和溢出风险的稳健版本。3.1 基础实现代码#include iostream #include algorithm using namespace std; typedef long long ll; // 定义long long的别名方便书写 int main() { ll n, k; cin n k; ll ans n * k; // 公式中的 n*k 部分 ll l 1, r; // l代表当前区间的左端点 // 数论分块主循环 while (l n) { if (k / l 0) break; // 当 k/l 为0时后面所有项贡献为0可提前结束 ll q k / l; // 当前区间统一的 ⌊k/l⌋ 值 r min(n, k / q); // 计算当前区间的右端点不能超过n // 计算区间[l, r]的贡献q * (l r) * (r - l 1) / 2 // 注意运算顺序先乘可能会溢出但这里用long long且n,k1e9时(lr)和(r-l1)都2e9乘积4e18在long long范围(约9e18)内 ll contrib q * (l r) * (r - l 1) / 2; ans - contrib; // 从总和中减去这部分贡献 l r 1; // 移动左端点到下一个区间的起点 } cout ans endl; return 0; }3.2 代码逐行解析与注意事项数据类型选择 (typedef long long ll)这是信奥竞赛中处理大数时的常见做法。int通常是32位范围大约是-2e9 ~ 2e9。n*k在n和k都为10^9时达到1e18远超int范围。long long是64位范围大约是-9e18 ~ 9e18足够安全。使用typedef定义别名ll可以让代码更简洁。输入与初始化 (cin n k; ll ans n * k;)直接读入n和k并初始化答案ans为n * k对应公式变换后的第一部分。循环条件与提前退出 (while (l n)和if (k / l 0) break;)while (l n)确保我们处理所有从1到n的i。 但是当l k时k / l整数除法结果为0。这意味着从当前的l开始直到n每一项i * ⌊k/i⌋都等于0因为⌊k/i⌋0。因此对总和的贡献为0没有必要继续循环可以直接break。这是一个重要的优化尤其当n远大于k时。计算右端点 (r min(n, k / q);)这是实现中最容易出错的一步。根据公式右端点r理论上等于⌊k / q⌋。但是这个值可能超过题目给定的n。因为我们的i只求和到n。所以必须用min(n, k / q)来保证右端点不超过n。计算区间贡献 (ll contrib q * (l r) * (r - l 1) / 2;)直接套用等差数列求和公式。这里涉及三个连续的乘法q * (l r) * (r - l 1)。在极限情况下例如l1,rn1e9,qk1e9这个乘积会达到1e9 * 2e9 * 1e9 2e27这显然超出了long long的范围。但是请注意我们的参数范围题目中n和k通常是10^9量级。(lr)最大约为2e9(r-l1)最大为1e9它们的乘积最大约为2e18。再乘以q(最大1e9)理论上限是2e27确实会溢出。然而在正确的数论分块中当l很小比如1时q k/l会很大但此时r也会很小r k/q。具体来说当l1时qkr min(n, k/k) 1。所以这个区间只有一项。乘积k * (11) * (1) / 2 k并不会溢出。实际上数论分块的性质保证了在计算每个区间时(lr)和(r-l1)不会同时很大。更严谨的分析可以证明中间结果不会超过long long的范围对于n,k 10^12都通常是安全的。但为了绝对安全一个更好的写法是ll contrib q * ( (l r) * (r - l 1) / 2 );或者先除2但要注意整除问题因为(lr)和(r-l1)中一定有一个是偶数所以(lr)*(r-l1)总是偶数可以先除2ll contrib q * ( (l r) / 2 * (r - l 1) );// 仅当(lr)为偶数时正确ll contrib q * ( (l r) * ((r - l 1) / 2) );// 仅当(r-l1)为偶数时正确 最稳妥的方法是使用__int128如果编译器支持或者像下面这样调整计算顺序并利用整数除法向下取整的特性但可能会引入精度问题。对于信奥竞赛n,k 10^9用long long直接相乘是安全的但知道这个潜在的溢出风险很重要。更新答案与左端点 (ans - contrib; l r 1;)从总和中减去当前区间的贡献然后将左端点移动到下一个区间的开始继续循环。3.3 稳健版本代码推荐下面是一个更加稳健的版本它显式处理了n和k的大小关系并添加了更清晰的注释。#include iostream #include algorithm using namespace std; typedef long long ll; int main() { ll n, k; cin n k; ll ans n * k; // 核心数论分块i从1开始但只需要处理到 min(n, k) // 因为当 i k 时k / i 0贡献为0 ll end min(n, k); ll l 1, r; while (l end) { ll q k / l; // 当前块的值 ⌊k/l⌋ r min(end, k / q); // 当前块的右端点 // 计算区间[l, r]的贡献值为q的项的和 q * (l ... r) // 等差数列求和公式sum (首项 末项) * 项数 / 2 ll sum_i (l r) * (r - l 1) / 2; // l到r的i的和 ll contrib q * sum_i; // 区间总贡献 ans - contrib; l r 1; // 跳到下一个块的起点 } // 注意如果 n k那么 i 从 k1 到 n 的部分k mod i k // 这部分在 ans n*k - ∑(i*⌊k/i⌋) 中由于 ⌊k/i⌋0所以 ∑部分为0ans已经包含了 n*k所以这部分实际上已经被正确计算了。 // 更直观的理解对于 i kk mod i k所以总和要加上 (n - k) * k。 // 但在我们的公式 ans n*k - ∑_{i1}^{min(n,k)} (i*⌊k/i⌋) 中当 ik 时⌊k/i⌋0所以求和项为0ans就是 n*k正好等于 (k mod i) 对 i1..k 的求和加上 (n-k)*k。 // 所以上面的循环只到 min(n,k) 就够了。 cout ans endl; return 0; }这个版本将循环终点明确设为min(n, k)逻辑更清晰。它同样正确处理了所有情况。4. 实战测试与边界情况分析理论正确不代表代码正确尤其是对于算法题边界情况Corner Cases往往是失分的重灾区。我们来设计几组测试数据验证我们的代码。4.1 测试用例设计样例测试题目通常会给出输入10 5输出29输入5 10输出20我们可以手动计算或写一个暴力程序验证。小数据测试验证基本逻辑n1, k1-1 mod 1 0输出应为0。n1, k100-100 mod 1 0输出0。n100, k1-∑(1 mod i)当i1时为0i1时为1。所以总和是99。公式ans 100*1 - ∑_{i1}^{100} (i * ⌊1/i⌋)。只有当i1时⌊1/1⌋1贡献1*11i2时⌊1/i⌋0。所以ans 100 - 1 99。相等情况nk。例如n100, k100。可以暴力验证。n 远大于 kn1e9, k1。根据上面分析结果应为n-1 999,999,999。我们的算法循环只到min(n,k)1只计算一个区间[1,1]贡献为1 * (1*1) 1ans 1e9 * 1 - 1 999,999,999。正确。k 远大于 nn5, k1e9。此时k/n很大。我们的算法需要正确处理多个分块。极大值测试检查溢出和时间n1e9, k1e9。这是时间复杂度的极限测试算法应在O(√1e9) ≈ 31623次循环内完成远低于1秒。n1e12, k1e12如果题目范围扩大。这时ans n*k 1e24已经超出long long范围约9e18需要使用__int128或高精度计算。但原题范围通常是1e9。4.2 常见错误与排查答案错误 (Wrong Answer)最可能的原因整数溢出。检查所有变量特别是ans、contrib、(lr)*(r-l1)是否使用了long long。确保输入n和k也用long long读取。检查右端点计算r min(n, k/q)是否写成了r k/q当k/q n时必须取n。检查循环条件如果写了while (l n l k)那么当n k时循环在lk1时停止这是正确的因为后面⌊k/i⌋0。但如果你在循环内用if (q 0) break也要确保q的计算是正确的。时间超限 (Time Limit Exceeded)这几乎不可能发生因为算法是O(√k)的。如果超时请检查是否写成了while (l n)且没有if (k/l 0) break或end min(n,k)的优化。当n很大而k很小时比如n1e9, k1如果没有优化循环会进行1e9次必然超时。我们的优化确保了循环最多min(n,k)次而内部分块又进一步降低了次数。运行错误 (Runtime Error)除零错误在计算q k / l时l在循环中从1开始递增不会为0。数组越界本题不需要数组。实操心得在信奥竞赛中对于数论分块题目在提交前务必测试n和k分别取最小值如1、最大值如1e9、nk、kn、nk这几种边界情况。自己写一个暴力的for循环程序用于生成小数据范围内的正确结果与你的优化算法进行对拍即用脚本随机生成大量小数据比较两个程序的输出这是发现隐蔽错误的最有效方法。5. 数论分块的延伸与总结通过这道题我们深入学习了数论分块整除分块技术。它的核心思想是发现⌊n/i⌋的值成块状分布并利用等差数列求和公式快速计算整块的和。这个技巧不仅用于求余数和还可以用于快速计算∑_{i1}^{n} ⌊n/i⌋、∑_{i1}^{n} i * ⌊n/i⌋等形式的和是解决许多数论问题的重要工具。最后分享一个我教学中学生最容易混淆的点在计算右端点r时公式r n / (n / l)是计算∑ ⌊n/i⌋时的标准形式。但在本题中我们求和的是∑ i * ⌊k/i⌋并且n和k是两个不同的数。所以右端点公式是r min(n, k / (k / l))。一定要分清分子分母牢记r不能超过n这个上限。把这个细节记牢这类题目就基本不会出错了。刷题不只是为了AC更是为了理解背后的思想。希望这篇详细的拆解能帮助你真正掌握“余数求和”这道题以及数论分块这个有力的工具。在信奥的道路上这类题目就像一块块基石扎实地掌握它们才能筑起解决更复杂问题的高楼。