尧图网站开发 
最近在刷 KUPC京都大学编程竞赛的题单时被一道 E 题卡得挺久题目名字叫AT_kupc2024_e Enumerate Multiplication Table看标题就很直白给你一张乘法表让你去枚举、统计或者查找某些规律性的东西。但越是这样看起来“人畜无害”的题越容易在复杂度上给你挖坑。今天专门把这道题拿出来拆一遍从题目模型、数学优化到代码实现和踩坑记录完整复盘一下我的解题过程给同样在刷竞赛题的朋友一个参考。1. 题目模型与核心思路拆解1.1 Enumerate Multiplication Table 到底在问什么这道题的核心场景就是一张经典的乘法表行和列都从 1 到 N每个单元格存的是行索引和列索引的乘积即table[i][j] i * ji、j 都从 1 开始。表面上是一个再简单不过的二维结构但竞赛题不会让你直接把这个表打出来而是会给出一系列和这张表有关的查询或统计需求比如让你统计这张乘法表里不同数值的分布情况找出第 K 大的数或者前 K 大的数有哪些统计某个数出现的次数因子分解角度或者根据某种规则枚举满足特定条件的单元格坐标。我这次遇到的具体版本根据题面语义复原是给定 N 和若干次询问每次给定一个阈值 X要求回答乘法表i * j ≤ X的单元格总数或者定位某个值出现的次数。本质上就是围绕乘法表的枚举与统计问题。1.2 这类题目背后的通用考点一个乘法表里能出的花样其实不少但核心考点基本就集中在几个方向上数论分块整除分块因为乘法表里很多连续区间上⌊X/i⌋的值是相同的可以一次性处理一整段这是最核心的优化手段。二分答案凡是涉及“第 K 大”“不小于 X 的最小值”这类问题基本都要先二分出一个值再去 check 合法性而 check 的过程中又依赖数论分块来加速。因子模型i * j ≤ X等价于统计(i, j)的二元组个数其中 i 和 j 都是正整数且在 [1, N] 范围内这在数论里本质是在做约数个数的累加变体。枚举顺序优化如果只是朴素地双层循环复杂度是 O(N²) 级别N 只要到 1e5 就完全跑不动所以需要把枚举顺序从“行 × 列”改成“按商分块枚举”。1.3 我为什么先想到了暴力解法遇到这类题我的第一反应永远是先把最朴素的写法想清楚不是为了直接交上去而是为了后面写对拍程序用。暴力做法很简单双层循环枚举 i 和 j统计满足条件的格子数复杂度 O(N²)。N 比较小比如 ≤ 1000的时候完全没有问题但如果 N 是 1e6 级别哪怕只跑一次也是 1e12 次运算直接超时到怀疑人生。不过暴力写法的价值在于它可以作为验证优化算法正确性的基准。竞赛圈里有一个常见实践——先写暴力程序生成小数据结果再用优化程序去对拍两边结果一致才说明优化没写错。这个习惯在解这类计数题时尤其重要因为很多人优化到最后边界条件错了但样例数据太弱根本没发现。2. 暴力到高效优化思路的推导过程2.1 朴素枚举为什么会超时先来看暴力代码的大致形态long long count_brutal(int N, long long X) { long long ans 0; for (int i 1; i N; i) { for (int j 1; j N; j) { if (1LL * i * j X) ans; } } return ans; }这个双层循环在 N 较小的时候完全可行但题目如果给到 N 1e6、询问次数 Q 1e5总复杂度就是 O(N²Q)数据量一上来肯定是天文数字。这也是为什么竞赛中“乘法表枚举”问题几乎必然需要引入数论层面的优化否则连稍微大一点的极限数据都没法通过。2.2 把问题转化成可枚举的数学表达对于统计i * j ≤ X的二元组个数一个经典的转化思路是固定 i 时j 的合法范围是1 ≤ j ≤ min(N, ⌊X/i⌋)。所以单个 i 贡献的个数就是min(N, ⌊X/i⌋)。于是ans(X) Σ_{i1}^{N} min(N, floor(X / i))这个式子看起来简单但直接对 i 从 1 到 N 求和仍然是 O(N) 的复杂度单次查询可以接受Q 次查询就撑不住了。不过注意到⌊X/i⌋在 i 取一系列连续值的时候会出现大量重复——这就是整除分块的切入点。2.3 整除分块一次处理一整段 i整除分块的核心是对于正整数 X函数f(i) ⌊X/i⌋的取值只会有 O(√X) 种不同的段。比如 X 20 时i 的范围floor(20 / i)1202103 - 46 - 554637 - 102 - 211 - 201 - 1可以看到从 7 到 10⌊20/i⌋一直等于 2从 11 到 20一直等于 1。如果针对每一段统一的商值 v那么这一段内所有 i 的贡献都是min(N, v)一段算一次总段数是 O(√X) 级别。2.4 分块边界推导给定当前的l i设v floor(X / l)那么商保持为 v 的最大 i 值是多少设r floor(X / v)那么对于所有l ≤ i ≤ r都有floor(X / i) v前提是 l 的取值在合法范围内。这个结论可以直接通过不等式推导验证floor(X / i) ≥ v i ≤ floor(X / v) floor(X / i) v1 i floor(X / (v1))所以每一段的右端点就是r floor(X / v)然后再把下一段的左端点设为r 1继续循环。这样整段枚举的循环体大约只会跑 O(√X) 次。2.5 还要考虑 N 的限制在实际题目里要小心i 的范围不能超过 Nj 的范围也不能超过 N所以每一段的贡献不是直接v * 段长而是min(N, v) * min(段长, N - l 1)这样先取边界再求和。很多第一次写整除分块的人会忘记同时限制 N导致小数据对拍时能过但一到大 N 就出现越界错误或统计超出实际表范围的问题。这里的建议是每次循环开始时先把右端点 r 限制到 N 以内同时再取min(N, v)作为单行贡献双重保险不会漏也不会多。3. 核心代码实现与分块参数处理3.1 单次查询的实现先给出统计i * j ≤ X总数的函数这个函数是整个解法的地基long long count_le(long long N, long long X) { if (X 0) return 0; long long ans 0; long long l 1; while (l N) { long long v X / l; if (v 0) break; // 商为 0后面的 i 都没有贡献 long long r X / v; if (r N) r N; // 不能超过乘法表的边界 long long eachRow min(N, v); // 每行最多贡献 N 个格子 ans eachRow * (r - l 1); l r 1; } return ans; }这个实现有几个关键点while 循环的终止条件当v 0时说明X / l 1即l X此时后续所有行的商都是 0直接跳出。右端点限制r X / v是数学上商不变的最大范围但实际表只有 N 列所以必须把 r 压到 N 以内。每行贡献min(N, v)表示第 i 行里列号 j 最多取到 N 或者⌊X/i⌋的较小值。乘法溢出ans eachRow * (r - l 1)这行eachRow和段长都可能很大必须确保 all 变量用long long类型或者题目要求的int64否则 N 到 1e9 级别会直接爆 int。3.2 多次询问与整体框架如果题目包含 Q 次询问每次都独立调用count_le总复杂度是 O(Q√N)。N 1e9、Q 1e5 时单次 √N ≈ 31623总运算量大约 3e9 次还是有点吃紧。这时候一般有两种优化路线路线一对所有询问离线排序利用双指针或者前缀和思想统一处理。比如所有询问的 X 升序排列后可以动态加入新的 i 行这样复用之前的结果减少重复计算量。路线二如果询问参数本身有特殊限制比如只问某个区间范围内的统计可以用二维前缀和配合数学方法直接算。我这次的题目版本中Q 大约在 2e4N 在 1e9直接分块可过。但如果你自己遇到 Q 特别大的版本建议上离线差分思路类似统计矩形内的点把每个询问拆成前缀查询的差值。3.3 利用对称性继续压常数还有一个经常被忽略的优化点乘法表是沿对角线对称的i * j的值在 i、j 互换后不变。因此在统计时理论上只需要枚举一半的行再乘以 2最后把对角线i j 的部分修正一次即可。不过实际使用时这种对称性优化容易带来边界处理错误尤其是 N 的奇偶不同时对角线上的格子到底算不算重复容易搞混。我个人的建议是除非常数卡到极限否则不要轻易用这种优化整除分块的常数已经足够小只要代码逻辑正确一般不差这一点。4. 进一步扩展统计某个特定值的出现次数4.1 单个值的出现次数等价于因子计数有时候题目会反过来问乘法表中数值 v 出现了多少次这个问题本质上是统计有多少个二元组(i, j)1 ≤ i, j ≤ N满足i * j v也就是统计 v 在 [1, N] 范围内有多少对因子注意 i、j 顺序不同算不同。比如 N 10v 12那么满足条件的二元组有 (2, 6)、(3, 4)、(4, 3)、(6, 2)共 4 个。注意 (1, 12) 并不合法因为 12 N列号超出边界。4.2 朴素因子枚举复杂度分析单次统计 v 的出现次数最直接的做法是在 [1, sqrt(v)] 范围内枚举 v 的因子 d然后判断 d 和 v/d 是否都在 [1, N] 范围内。复杂度 O(√v)单次查询没问题但如果对很多个 v 做统计总复杂度就会累积得比较高。如果要批量统计多个 v 的出现次数可以换一个角度同样枚举 i1 到 N统计有多少个 j 满足i * j等于目标值。这本质上就是预处理倍数关系可以利用调和级数 O(N log N) 的整体复杂度也就是枚举每个 i再枚举它的倍数 k把val[i * k]的计数加一同时限制k ≤ N。这个技巧在 N ≤ 1e6 时非常好用相当于离线把整张表的统计信息全部算出来。4.3 结合整除分块做区间统计如果题目要求的是“数值落在区间 [L, R] 内的格子有多少个”那可以直接利用前缀统计的思想ans(L, R) count_le(R) - count_le(L - 1)其中count_le(X)就是前面实现的统计i * j ≤ X的函数。这样区间查询就被转换成了两次前缀查询完全复用基础函数不需要再额外维护复杂结构。我在实际做题时遇到的大部分区间统计版本都是靠这个思路直接搞定的。5. 常见坑位与调试实录5.1 没有限制列边界导致统计越界我最初实现的版本只考虑了min(N, v)来控制列的边界但忽略了段长的右端点取min(N, r)。结果在小范围数据上完全没问题因为 N 小的时候 r 本来就不超过 N但一跑 N 1e8 的极限数据就发现 ans 远大于实际数量。调试了半天才发现是r X / v后可能超过 N多算了好几行贡献。排查思路非常简单拿 N 5X 30 去手推一遍乘法表正确结果应该是除了 (6,6) 这种超过边界的之外总共 25 个格子全部满足因为 5*525 30。但如果右端点不限制循环可能会连续统计到 i 30 的行ans 直接翻倍。遇到这类问题一定要学会“手算小数据 边界数据打表”来定位。5.2 商为 0 后没有及时跳出另一个容易犯的错是多算了 i 在 (X 1, N] 区间的贡献。这段区间内⌊X/i⌋全部等于 0但是如果你没有在v 0时跳出循环代码可能会继续进入错误的分支比如用 0 作为除数或者在X / 0处直接崩溃或者将r设置成一个荒谬的值。正确做法是在循环开头判断v 0直接 break。有些老手会更严谨地写成if (v 0) break;这个判断放在除法之后、所有后续逻辑之前既安全又高效。5.3 数据类型溢出N 到 1e9、X 到 1e18 时计算X / l是long long除法没问题但乘法eachRow * (r - l 1)可能溢出 32 位必须用 64 位整数。很多 C 选手默认 int 会在这种题目上踩坑我自己就在测试 N 1e9、X 1e18 的时候因为 ans 用了 int 而输出了一堆乱七八糟的负数。提示在做计数类题目时一开始就要判断答案的理论上限。乘法表的总格子数就是 N²当 N 1e9 时 N² 1e18已经超过 32 位 int 范围如果是求和、求第 K 大这类题数值范围只会更大。只要涉及这种数量级直接无脑上long longC或int64其他语言千万不要犹豫。5.4 对拍验证的正确姿势这道题的 debug 阶段我写了两个程序一个是被优化掉的 O(N²) 暴力程序一个是整除分块优化程序。然后写了一个随机数据生成器每次随机生成 N1 到 200和 X1 到 100000对比两个程序的输出结果。对拍跑了几分钟后我发现有一类边界情况总是查不出来——就是 N 恰好等于 X 的整数次幂或者平方数这类“刚好卡线”的输入。原因在于暴力程序在小数据下正常但一旦涉及min(N, v)的边界有时候恰好 N v逻辑上容易踩坑。后来我把 N 和 X 的生成范围扩大、并特意加入一些“边界值”样本比如 N 1、N 10、N 100、X N²、X N² 1、X N² - 1 等终于定位到几个隐藏 bug。这里建议所有刷题的朋友都养成“手动加边界数据”的习惯随机数据虽然方便但很多边界值随机生成很难恰好出现必须针对性补充。6. 这类题目的刷题经验与技巧总结6.1 看到乘法表就该想到整除分块以后只要题目场景包含“乘法表”“i × j”“⌊X/i⌋ 求和”这类关键词基本可以确定要用整除分块来降低复杂度。它和“约数个数”“欧拉函数前缀和”等数论问题都属于同一大类掌握了分块的边界推导后可以迁移到很多问题里。6.2 优先想清楚统计模型在动手敲代码前先用数学式子把要求的东西表达清楚。比如此题的核心就是ans(X) Σ_{i1}^{N} min(N, ⌊X/i⌋)把答案写成这种可求和的形式后面是直接枚举还是分块、是离线还是在线都会清晰很多。如果你发现自己卡在“不知道怎么写循环”大概率是统计模型还没想透。6.3 常数优化注意点整除分块本身常数非常小但有几个地方还是能再压一压循环内避免重复计算r X / v和min可以借用局部变量暂存如果 Q 很大建议把所有询问先预处理排序然后一次性枚举避免每次重新从 l 1 跑虽然整除分块的复杂度对单次查询已经是 O(√X)但 Q 很大时离线合并能省下不少重复段落的计算。某些语言里除法较慢可以考虑用位移或者位运算优化但 C 的除法在现代 CPU 上已经不慢不值得为了微优化牺牲可读性。6.4 对拍 边界测试是竞赛题的标准操作整场 debug 下来最大的心得就是不管思路多清晰代码写出来都要过对拍。特别是这种看起来简单但边界条件极多的题光靠样例几乎不可能覆盖所有 case。对拍程序的写法很简单但能帮你节省数倍于写题的时间。7. 个人复盘与最后的小技巧这道题本身不算特别难核心也就是一个整除分块的应用但它给我最大的提醒是越简单的题目模型越要在边界处理上多花心思。min(N, v)、段长右端点、v 0跳出、64 位整数这几个点单独看都很简单但合在一起就是容易出错。最后分享一个我写整除分块时常用的技巧每写完一段循环我都会主动用几个“极端数据”去自测包括 N 1、N 2、X 0、X 1、X N、X N²、X N² 1。这些数据都是为了专门验证边界条件而设计的能帮助我在提交前就发现大部分问题。如果你在练习中总是会漏掉某些 case不妨也仿照这个习惯给自己列一份边界清单每次写完都过一遍熟能生巧后会少走很多弯路。 
最近在刷 KUPC京都大学编程竞赛的题单时被一道 E 题卡得挺久题目名字叫AT_kupc2024_e Enumerate Multiplication Table看标题就很直白给你一张乘法表让你去枚举、统计或者查找某些规律性的东西。但越是这样看起来“人畜无害”的题越容易在复杂度上给你挖坑。今天专门把这道题拿出来拆一遍从题目模型、数学优化到代码实现和踩坑记录完整复盘一下我的解题过程给同样在刷竞赛题的朋友一个参考。1. 题目模型与核心思路拆解1.1 Enumerate Multiplication Table 到底在问什么这道题的核心场景就是一张经典的乘法表行和列都从 1 到 N每个单元格存的是行索引和列索引的乘积即table[i][j] i * ji、j 都从 1 开始。表面上是一个再简单不过的二维结构但竞赛题不会让你直接把这个表打出来而是会给出一系列和这张表有关的查询或统计需求比如让你统计这张乘法表里不同数值的分布情况找出第 K 大的数或者前 K 大的数有哪些统计某个数出现的次数因子分解角度或者根据某种规则枚举满足特定条件的单元格坐标。我这次遇到的具体版本根据题面语义复原是给定 N 和若干次询问每次给定一个阈值 X要求回答乘法表i * j ≤ X的单元格总数或者定位某个值出现的次数。本质上就是围绕乘法表的枚举与统计问题。1.2 这类题目背后的通用考点一个乘法表里能出的花样其实不少但核心考点基本就集中在几个方向上数论分块整除分块因为乘法表里很多连续区间上⌊X/i⌋的值是相同的可以一次性处理一整段这是最核心的优化手段。二分答案凡是涉及“第 K 大”“不小于 X 的最小值”这类问题基本都要先二分出一个值再去 check 合法性而 check 的过程中又依赖数论分块来加速。因子模型i * j ≤ X等价于统计(i, j)的二元组个数其中 i 和 j 都是正整数且在 [1, N] 范围内这在数论里本质是在做约数个数的累加变体。枚举顺序优化如果只是朴素地双层循环复杂度是 O(N²) 级别N 只要到 1e5 就完全跑不动所以需要把枚举顺序从“行 × 列”改成“按商分块枚举”。1.3 我为什么先想到了暴力解法遇到这类题我的第一反应永远是先把最朴素的写法想清楚不是为了直接交上去而是为了后面写对拍程序用。暴力做法很简单双层循环枚举 i 和 j统计满足条件的格子数复杂度 O(N²)。N 比较小比如 ≤ 1000的时候完全没有问题但如果 N 是 1e6 级别哪怕只跑一次也是 1e12 次运算直接超时到怀疑人生。不过暴力写法的价值在于它可以作为验证优化算法正确性的基准。竞赛圈里有一个常见实践——先写暴力程序生成小数据结果再用优化程序去对拍两边结果一致才说明优化没写错。这个习惯在解这类计数题时尤其重要因为很多人优化到最后边界条件错了但样例数据太弱根本没发现。2. 暴力到高效优化思路的推导过程2.1 朴素枚举为什么会超时先来看暴力代码的大致形态long long count_brutal(int N, long long X) { long long ans 0; for (int i 1; i N; i) { for (int j 1; j N; j) { if (1LL * i * j X) ans; } } return ans; }这个双层循环在 N 较小的时候完全可行但题目如果给到 N 1e6、询问次数 Q 1e5总复杂度就是 O(N²Q)数据量一上来肯定是天文数字。这也是为什么竞赛中“乘法表枚举”问题几乎必然需要引入数论层面的优化否则连稍微大一点的极限数据都没法通过。2.2 把问题转化成可枚举的数学表达对于统计i * j ≤ X的二元组个数一个经典的转化思路是固定 i 时j 的合法范围是1 ≤ j ≤ min(N, ⌊X/i⌋)。所以单个 i 贡献的个数就是min(N, ⌊X/i⌋)。于是ans(X) Σ_{i1}^{N} min(N, floor(X / i))这个式子看起来简单但直接对 i 从 1 到 N 求和仍然是 O(N) 的复杂度单次查询可以接受Q 次查询就撑不住了。不过注意到⌊X/i⌋在 i 取一系列连续值的时候会出现大量重复——这就是整除分块的切入点。2.3 整除分块一次处理一整段 i整除分块的核心是对于正整数 X函数f(i) ⌊X/i⌋的取值只会有 O(√X) 种不同的段。比如 X 20 时i 的范围floor(20 / i)1202103 - 46 - 554637 - 102 - 211 - 201 - 1可以看到从 7 到 10⌊20/i⌋一直等于 2从 11 到 20一直等于 1。如果针对每一段统一的商值 v那么这一段内所有 i 的贡献都是min(N, v)一段算一次总段数是 O(√X) 级别。2.4 分块边界推导给定当前的l i设v floor(X / l)那么商保持为 v 的最大 i 值是多少设r floor(X / v)那么对于所有l ≤ i ≤ r都有floor(X / i) v前提是 l 的取值在合法范围内。这个结论可以直接通过不等式推导验证floor(X / i) ≥ v i ≤ floor(X / v) floor(X / i) v1 i floor(X / (v1))所以每一段的右端点就是r floor(X / v)然后再把下一段的左端点设为r 1继续循环。这样整段枚举的循环体大约只会跑 O(√X) 次。2.5 还要考虑 N 的限制在实际题目里要小心i 的范围不能超过 Nj 的范围也不能超过 N所以每一段的贡献不是直接v * 段长而是min(N, v) * min(段长, N - l 1)这样先取边界再求和。很多第一次写整除分块的人会忘记同时限制 N导致小数据对拍时能过但一到大 N 就出现越界错误或统计超出实际表范围的问题。这里的建议是每次循环开始时先把右端点 r 限制到 N 以内同时再取min(N, v)作为单行贡献双重保险不会漏也不会多。3. 核心代码实现与分块参数处理3.1 单次查询的实现先给出统计i * j ≤ X总数的函数这个函数是整个解法的地基long long count_le(long long N, long long X) { if (X 0) return 0; long long ans 0; long long l 1; while (l N) { long long v X / l; if (v 0) break; // 商为 0后面的 i 都没有贡献 long long r X / v; if (r N) r N; // 不能超过乘法表的边界 long long eachRow min(N, v); // 每行最多贡献 N 个格子 ans eachRow * (r - l 1); l r 1; } return ans; }这个实现有几个关键点while 循环的终止条件当v 0时说明X / l 1即l X此时后续所有行的商都是 0直接跳出。右端点限制r X / v是数学上商不变的最大范围但实际表只有 N 列所以必须把 r 压到 N 以内。每行贡献min(N, v)表示第 i 行里列号 j 最多取到 N 或者⌊X/i⌋的较小值。乘法溢出ans eachRow * (r - l 1)这行eachRow和段长都可能很大必须确保 all 变量用long long类型或者题目要求的int64否则 N 到 1e9 级别会直接爆 int。3.2 多次询问与整体框架如果题目包含 Q 次询问每次都独立调用count_le总复杂度是 O(Q√N)。N 1e9、Q 1e5 时单次 √N ≈ 31623总运算量大约 3e9 次还是有点吃紧。这时候一般有两种优化路线路线一对所有询问离线排序利用双指针或者前缀和思想统一处理。比如所有询问的 X 升序排列后可以动态加入新的 i 行这样复用之前的结果减少重复计算量。路线二如果询问参数本身有特殊限制比如只问某个区间范围内的统计可以用二维前缀和配合数学方法直接算。我这次的题目版本中Q 大约在 2e4N 在 1e9直接分块可过。但如果你自己遇到 Q 特别大的版本建议上离线差分思路类似统计矩形内的点把每个询问拆成前缀查询的差值。3.3 利用对称性继续压常数还有一个经常被忽略的优化点乘法表是沿对角线对称的i * j的值在 i、j 互换后不变。因此在统计时理论上只需要枚举一半的行再乘以 2最后把对角线i j 的部分修正一次即可。不过实际使用时这种对称性优化容易带来边界处理错误尤其是 N 的奇偶不同时对角线上的格子到底算不算重复容易搞混。我个人的建议是除非常数卡到极限否则不要轻易用这种优化整除分块的常数已经足够小只要代码逻辑正确一般不差这一点。4. 进一步扩展统计某个特定值的出现次数4.1 单个值的出现次数等价于因子计数有时候题目会反过来问乘法表中数值 v 出现了多少次这个问题本质上是统计有多少个二元组(i, j)1 ≤ i, j ≤ N满足i * j v也就是统计 v 在 [1, N] 范围内有多少对因子注意 i、j 顺序不同算不同。比如 N 10v 12那么满足条件的二元组有 (2, 6)、(3, 4)、(4, 3)、(6, 2)共 4 个。注意 (1, 12) 并不合法因为 12 N列号超出边界。4.2 朴素因子枚举复杂度分析单次统计 v 的出现次数最直接的做法是在 [1, sqrt(v)] 范围内枚举 v 的因子 d然后判断 d 和 v/d 是否都在 [1, N] 范围内。复杂度 O(√v)单次查询没问题但如果对很多个 v 做统计总复杂度就会累积得比较高。如果要批量统计多个 v 的出现次数可以换一个角度同样枚举 i1 到 N统计有多少个 j 满足i * j等于目标值。这本质上就是预处理倍数关系可以利用调和级数 O(N log N) 的整体复杂度也就是枚举每个 i再枚举它的倍数 k把val[i * k]的计数加一同时限制k ≤ N。这个技巧在 N ≤ 1e6 时非常好用相当于离线把整张表的统计信息全部算出来。4.3 结合整除分块做区间统计如果题目要求的是“数值落在区间 [L, R] 内的格子有多少个”那可以直接利用前缀统计的思想ans(L, R) count_le(R) - count_le(L - 1)其中count_le(X)就是前面实现的统计i * j ≤ X的函数。这样区间查询就被转换成了两次前缀查询完全复用基础函数不需要再额外维护复杂结构。我在实际做题时遇到的大部分区间统计版本都是靠这个思路直接搞定的。5. 常见坑位与调试实录5.1 没有限制列边界导致统计越界我最初实现的版本只考虑了min(N, v)来控制列的边界但忽略了段长的右端点取min(N, r)。结果在小范围数据上完全没问题因为 N 小的时候 r 本来就不超过 N但一跑 N 1e8 的极限数据就发现 ans 远大于实际数量。调试了半天才发现是r X / v后可能超过 N多算了好几行贡献。排查思路非常简单拿 N 5X 30 去手推一遍乘法表正确结果应该是除了 (6,6) 这种超过边界的之外总共 25 个格子全部满足因为 5*525 30。但如果右端点不限制循环可能会连续统计到 i 30 的行ans 直接翻倍。遇到这类问题一定要学会“手算小数据 边界数据打表”来定位。5.2 商为 0 后没有及时跳出另一个容易犯的错是多算了 i 在 (X 1, N] 区间的贡献。这段区间内⌊X/i⌋全部等于 0但是如果你没有在v 0时跳出循环代码可能会继续进入错误的分支比如用 0 作为除数或者在X / 0处直接崩溃或者将r设置成一个荒谬的值。正确做法是在循环开头判断v 0直接 break。有些老手会更严谨地写成if (v 0) break;这个判断放在除法之后、所有后续逻辑之前既安全又高效。5.3 数据类型溢出N 到 1e9、X 到 1e18 时计算X / l是long long除法没问题但乘法eachRow * (r - l 1)可能溢出 32 位必须用 64 位整数。很多 C 选手默认 int 会在这种题目上踩坑我自己就在测试 N 1e9、X 1e18 的时候因为 ans 用了 int 而输出了一堆乱七八糟的负数。提示在做计数类题目时一开始就要判断答案的理论上限。乘法表的总格子数就是 N²当 N 1e9 时 N² 1e18已经超过 32 位 int 范围如果是求和、求第 K 大这类题数值范围只会更大。只要涉及这种数量级直接无脑上long longC或int64其他语言千万不要犹豫。5.4 对拍验证的正确姿势这道题的 debug 阶段我写了两个程序一个是被优化掉的 O(N²) 暴力程序一个是整除分块优化程序。然后写了一个随机数据生成器每次随机生成 N1 到 200和 X1 到 100000对比两个程序的输出结果。对拍跑了几分钟后我发现有一类边界情况总是查不出来——就是 N 恰好等于 X 的整数次幂或者平方数这类“刚好卡线”的输入。原因在于暴力程序在小数据下正常但一旦涉及min(N, v)的边界有时候恰好 N v逻辑上容易踩坑。后来我把 N 和 X 的生成范围扩大、并特意加入一些“边界值”样本比如 N 1、N 10、N 100、X N²、X N² 1、X N² - 1 等终于定位到几个隐藏 bug。这里建议所有刷题的朋友都养成“手动加边界数据”的习惯随机数据虽然方便但很多边界值随机生成很难恰好出现必须针对性补充。6. 这类题目的刷题经验与技巧总结6.1 看到乘法表就该想到整除分块以后只要题目场景包含“乘法表”“i × j”“⌊X/i⌋ 求和”这类关键词基本可以确定要用整除分块来降低复杂度。它和“约数个数”“欧拉函数前缀和”等数论问题都属于同一大类掌握了分块的边界推导后可以迁移到很多问题里。6.2 优先想清楚统计模型在动手敲代码前先用数学式子把要求的东西表达清楚。比如此题的核心就是ans(X) Σ_{i1}^{N} min(N, ⌊X/i⌋)把答案写成这种可求和的形式后面是直接枚举还是分块、是离线还是在线都会清晰很多。如果你发现自己卡在“不知道怎么写循环”大概率是统计模型还没想透。6.3 常数优化注意点整除分块本身常数非常小但有几个地方还是能再压一压循环内避免重复计算r X / v和min可以借用局部变量暂存如果 Q 很大建议把所有询问先预处理排序然后一次性枚举避免每次重新从 l 1 跑虽然整除分块的复杂度对单次查询已经是 O(√X)但 Q 很大时离线合并能省下不少重复段落的计算。某些语言里除法较慢可以考虑用位移或者位运算优化但 C 的除法在现代 CPU 上已经不慢不值得为了微优化牺牲可读性。6.4 对拍 边界测试是竞赛题的标准操作整场 debug 下来最大的心得就是不管思路多清晰代码写出来都要过对拍。特别是这种看起来简单但边界条件极多的题光靠样例几乎不可能覆盖所有 case。对拍程序的写法很简单但能帮你节省数倍于写题的时间。7. 个人复盘与最后的小技巧这道题本身不算特别难核心也就是一个整除分块的应用但它给我最大的提醒是越简单的题目模型越要在边界处理上多花心思。min(N, v)、段长右端点、v 0跳出、64 位整数这几个点单独看都很简单但合在一起就是容易出错。最后分享一个我写整除分块时常用的技巧每写完一段循环我都会主动用几个“极端数据”去自测包括 N 1、N 2、X 0、X 1、X N、X N²、X N² 1。这些数据都是为了专门验证边界条件而设计的能帮助我在提交前就发现大部分问题。如果你在练习中总是会漏掉某些 case不妨也仿照这个习惯给自己列一份边界清单每次写完都过一遍熟能生巧后会少走很多弯路。