企业官网建设流程全解析

最近在刷 KUPC（京都大学编程竞赛）的题单时，被一道 E 题卡得挺久，题目名字叫AT_kupc2024_e Enumerate Multiplication Table，看标题就很直白：给你一张乘法表，让你去枚举、统计或者查找某些规律性的东西。但越是这样看起来“人畜无害”的题，越容易在复杂度上给你挖坑。今天专门把这道题拿出来拆一遍，从题目模型、数学优化到代码实现和踩坑记录，完整复盘一下我的解题过程，给同样在刷竞赛题的朋友一个参考。

1. 题目模型与核心思路拆解

1.1 Enumerate Multiplication Table 到底在问什么

这道题的核心场景就是一张经典的乘法表：行和列都从 1 到 N，每个单元格存的是行索引和列索引的乘积，即table[i][j] = i * j（i、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) = Σ_{i=1}^{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 时：

可以看到，从 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) < v+1 <=> i > floor(X / (v+1))

所以每一段的右端点就是r = floor(X / v)，然后再把下一段的左端点设为r + 1继续循环。这样整段枚举的循环体大约只会跑 O(√X) 次。

2.5 还要考虑 N 的限制

在实际题目里要小心：i 的范围不能超过 N，j 的范围也不能超过 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 大约在 2e4，N 在 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 = 10，v = 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 的出现次数，可以换一个角度：同样枚举 i（1 到 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 = 5，X = 30 去手推一遍乘法表，正确结果应该是除了 (6,6) 这种超过边界的之外，总共 25 个格子全部满足（因为 5*5=25 < 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 long（C++）或int64（其他语言），千万不要犹豫。

5.4 对拍验证的正确姿势

这道题的 debug 阶段我写了两个程序：一个是被优化掉的 O(N²) 暴力程序，一个是整除分块优化程序。然后写了一个随机数据生成器，每次随机生成 N（1 到 200）和 X（1 到 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) = Σ_{i=1}^{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，不妨也仿照这个习惯，给自己列一份边界清单，每次写完都过一遍，熟能生巧后会少走很多弯路。