值域统计解法:用频次数组+倍数枚举破解Not Divisible问题 1. 这道题为什么让很多人卡在“看似简单”的陷阱里AtCoder Beginner Contest 170 的 D 题 “Not Divisible” 表面看就是个筛法变形题——给定 N 个正整数找出其中“不被其他任何数整除”的数的个数。初看甚至会下意识想直接两重循环暴力判断每个 a[i] 是否被其余所有 a[j] 整除时间复杂度 O(N²)N ≤ 2×10⁵那肯定超时。于是立刻转向埃氏筛或线性筛思路但很快发现这不是筛质数也不是筛倍数而是要判断“在给定集合内部”某个数是否是集合中其他数的真因数即存在 j ≠ i 使得 a[j] % a[i] 0。这个“内部相对性”彻底改变了问题性质。我第一次提交就栽在这儿。当时用了一个常见误区先对数组排序然后对每个数 a[i]只检查它前面更小的数能否整除它——逻辑上似乎合理因为只有更小的数才可能整除它。但漏掉了关键一点集合中可能存在重复值。比如输入是 [2, 2, 4]排序后是 [2, 2, 4]。当处理第二个 2 时前面有第一个 2而 2 % 2 0所以第二个 2 被判为“可被整除”正确但当处理第一个 2 时它前面没有数就被误判为“不可被整除”而实际上第二个 2 就是它的“其他数”。这就导致答案多算 1。这个细节在 AtCoder 官方样例里藏得很深很多选手直到 WA 了三次才意识到。更隐蔽的坑在于数据范围。题目明确说 a[i] ≤ 2×10⁵但 N 本身可以达到 2×10⁵。这意味着最坏情况下你可能要处理 20 万个各不相同的数最大值逼近 20 万。如果盲目对每个数都去枚举它的所有倍数像传统筛法那样总操作次数会飙升到 Σ(2×10⁵ / a[i])当 a[i] 大量集中在 1、2、3 附近时这个和会远超 10⁷稳稳 TLE。所以必须设计一种能利用“值域有限”这一特性的方案而不是单纯依赖“N 不大”。这道题真正考验的不是你会不会写 for 循环而是你能否在 5 分钟内完成三重思维切换从“暴力模拟”跳到“值域统计”再跳到“逆向标记”最后还要稳住心态处理好边界——比如 1 这个数它能整除所有数所以只要集合里有大于 1 的数1 就一定不是答案但如果整个集合全是 1 呢那每个 1 都会被其他 1 整除所以答案是 0。这种边界 case 在赛中极易手抖写错。提示别急着写代码。先在纸上模拟 [1,2,3,4,5,6] 和 [2,2,4,8] 这两组数据手动走一遍你设想的算法把每一步的中间状态记下来。你会发现90% 的 WA 都源于对“其他数”这个条件的理解偏差。2. 核心解法拆解为什么必须用“频次数组 倍数遍历”而非“排序 双指针”这道题的标准解法本质是把“判断每个 a[i] 是否被集合中其他数整除”这个 O(N²) 的问题通过值域压缩转化成一个 O(M log M) 的问题其中 M 是 a[i] 的最大值本题为 2×10⁵。这个转化的关键在于彻底放弃“以数组下标为单位”的思考转而以“数值本身为单位”进行统计和推演。2.1 第一步构建频次数组 count[x]而非直接操作原数组我们定义一个长度为 MAX_A1 的数组 count其中 count[x] 表示数值 x 在输入中出现的次数。例如输入 [2,2,4,8]则 count[2]2count[4]1count[8]1其余为 0。这步操作的时间复杂度是 O(N)空间是 O(MAX_A)。为什么要这么做因为原问题中的“其他数”指的是“集合中除它自身外的任意一个数”。对于一个值为 x 的数它是否“Not Divisible”取决于是否存在另一个值为 y 的数使得 y % x 0 且 y ≠ x。注意这里 y 可以等于 x只要它在集合中出现了至少两次——这就是之前提到的重复值陷阱。所以对于值 x我们真正需要知道的是所有 x 的倍数 yy x的总出现次数加上如果 count[x] 1则 x 自身的“其他”出现次数。如果这个总和大于 0那么任意一个值为 x 的数都不是“Not Divisible”。2.2 第二步对每个可能的 x枚举其所有倍数 y并累加 count[y]这才是算法的主干。伪代码如下ans 0 for x from 1 to MAX_A: if count[x] 0: continue # x 根本没出现跳过 total_multiples 0 # 枚举 x 的所有倍数 y 2x, 3x, 4x, ... MAX_A for y from 2*x to MAX_A step x: total_multiples count[y] # 如果 x 出现了多次那么除了倍数x 自身的其他出现也是“其他数” if count[x] 1: total_multiples (count[x] - 1) # 如果 total_multiples 为 0说明没有任何“其他数”能被 x 整除 if total_multiples 0: ans count[x] # 所有值为 x 的数都符合条件这个双重循环的复杂度是经典的调和级数求和Σ_{x1}^{M} (M/x) ≈ M × H_M ≈ M × ln M。当 M 2×10⁵ 时ln(2×10⁵) ≈ 12.2所以总操作数约为 2.4×10⁶完全在安全范围内。2.3 为什么排序双指针在这里失效有人会想先排序然后对每个位置 i用双指针找所有 j i 使得 a[j] 整除 a[i]。这看似能避免重复计算但问题在于“整除关系”不是单向有序的。例如排序后数组是 [2,3,4,6,8,12]当处理 12 时你需要检查 2、3、4、6、8 是否整除它。但 8 并不整除 12而 6 可以。双指针无法高效地“跳跃”到所有因数位置因为你无法预知 12 的因数在排序数组中的分布——它们是稀疏且无规律的。你最终还是会退化成对每个 i遍历所有 j i回到 O(N²)。另一种尝试是“对每个 a[i]分解质因数然后生成所有因数”这在理论上可行但实际中一个数最多有约 100 个因数对于 2×10⁵ 内的数而 N 是 2×10⁵总操作数就是 2×10⁷已经接近时限边缘且因数生成和哈希查找的常数很大实测非常容易 TLE。相比之下倍数枚举的常数极小CPU 缓存友好是经过千锤百炼的工业级选择。注意在实现倍数枚举时内层循环的起始点必须是2*x而不是x。因为y x对应的是它自身而我们需要的是“其他数”。这是代码中最容易写错的一行建议在循环开始前加一行注释// y must be x to be other number。3. 实操细节与避坑指南从本地测试到 AtCoder 提交的全流程光懂原理还不够从写第一行代码到 AC中间有太多“看似微小却致命”的细节。我整理了自己和身边选手踩过的所有坑按开发流程顺序排列。3.1 输入与频次数组初始化MAX_A 的取值必须精确题目说 a[i] ≤ 2×10⁵所以直觉上设MAX_A 200000。但请务必检查输入样例AtCoder 的样例输入里a[i] 的最大值可能远小于这个数。如果你为了省事把count数组开得过大比如MAX_A 1000000虽然不会出错但会浪费大量内存和初始化时间。反之如果开小了比如MAX_A 199999遇到恰好是 200000 的数据就会越界。最佳实践是先读入所有 N 个数记录下max_val max(a[i])然后MAX_A max_val。这样既精准又高效。在 C 中可以用vectorint count(max_val 1, 0)在 Python 中用count [0] * (max_val 1)。注意数组索引是从 0 开始的所以长度必须是max_val 1否则count[max_val]会越界。3.2 倍数枚举的边界控制避免整数溢出与无效访问内层循环for y in range(2*x, MAX_A1, x)看似简单但有两个隐藏雷区雷区一2*x可能超过MAX_A。如果x很大比如x 100001那么2*x 200002 MAX_A此时循环体一次都不会执行total_multiples保持为 0如果count[x] 1这个 x 就会被错误计入答案。但实际上如果x MAX_A/2它的最小倍数2*x已经超出值域所以它不可能被集合中任何其他数整除因为其他数最大就是MAX_A因此它天然满足“Not Divisible”条件。所以这个逻辑本身是对的但你需要确保循环的range函数不会因为2*x MAX_A而抛出异常。Python 的range会自动处理但 C 的for (int y 2*x; y MAX_A; y x)则完全安全。雷区二y的取值必须严格 ≤MAX_A。这是常识但新手常犯的错误是写成y MAX_A导致count[MAX_A]永远不会被累加。务必用y MAX_A或y max_val。3.3 重复值的终极处理count[x] 1的分支逻辑这是本题最核心的区分点。让我们用 [2,2,4] 来彻底讲清count[2] 2,count[4] 1当x 2倍数y:4(因为2*24 4) →total_multiples count[4] 1因为count[2] 1所以total_multiples (2-1) 1最终total_multiples 2 0→ 所有值为 2 的数都不符合ans 0当x 4倍数y:2*48 4所以没有倍数 →total_multiples 0count[4] 1不进入1分支total_multiples 0→ans count[4] 1答案是 1正确。关键在于count[x] 1这个分支是在补全“x 自身作为其他数”的情况。它和倍数是并列关系不是互斥关系。很多选手会错误地写成if count[x] 1: total_multiples count[x] - 1 else: ...这会导致漏掉倍数贡献。3.4 输出与调试如何快速定位 WA 的具体位置AtCoder 的测试用例不公开WA 后只能靠猜。一个高效的调试策略是写一个小型的brute_force函数对小数据N ≤ 100用 O(N²) 暴力跑一遍和你的主函数结果对比。def brute_force(a): n len(a) res 0 for i in range(n): is_not_divisible True for j in range(n): if i j: continue if a[j] % a[i] 0: is_not_divisible False break if is_not_divisible: res 1 return res然后在主函数里当N 100时同时运行brute_force和你的solve如果结果不同就print(WA on, a)并exit()。这样你就能在本地复现 WA 的输入从而精准 debug。经验我在赛中曾因为一个写成了导致对x1的处理出错。x1是个魔鬼数字因为它能整除所有数。所以count[1] 0时total_multiples一定是sum(count[2:]) (count[1]-1)几乎总是大于 0。唯一例外是整个数组都是 1此时count[1] Ntotal_multiples (N-1)只要 N1答案就是 0。这个 case 必须单独验证。4. 进阶优化与同类题型迁移从 ABC 170-D 到更广阔的算法世界掌握了这道题的核心思想你就获得了一把打开“值域统计类”问题的钥匙。这类问题的共性是输入规模 N 很大但数值范围 M 相对较小且问题本质与“数的倍数/因数关系”相关。下面我分享几个实战中验证过的优化技巧和延伸方向。4.1 优化一提前终止的“倍数剪枝”标准解法中对每个 x我们都要枚举2x, 3x, ...。但很多时候一旦total_multiples已经大于 0后续的累加就毫无意义。所以可以在内层循环中加入提前退出total_multiples 0 y 2 * x while y MAX_A: total_multiples count[y] if total_multiples 0 and count[x] 1: # 如果 x 只出现一次且已经有倍数存在就可以提前退出 break y x # 之后再处理 count[x] 1 的情况 if count[x] 1: total_multiples (count[x] - 1)这个优化在大数据集上效果显著。例如当 x1 时count[1]通常很大但total_multiples在y2时就变成count[2]如果count[2] 0循环立刻结束避免了遍历 20 万个倍数。4.2 优化二使用布尔数组替代计数节省内存与时间如果题目只问“有多少个数满足条件”而不关心具体是哪些数那么count[x]的作用仅仅是告诉我们 x 是否存在以及是否存在重复。我们可以用两个布尔数组代替exists[x]: x 是否在输入中出现过duplicated[x]: x 是否出现过至少两次这样内存从O(MAX_A)的整数数组降为O(MAX_A)的布尔数组实际内存占用减半且total_multiples的计算也简化为逻辑或OR操作只要exists[y]为真或者duplicated[x]为真total_multiples就为真。这在 C 中可以用bitset实现在 Python 中可以用set配合in操作但要注意in对set是 O(1)对list是 O(N)千万别用错。4.3 迁移应用三道高度相似的 AtCoder/Codeforces 真题这道题的思想在竞赛中反复出现只是包装略有不同ABC 164-D Multiple of 2019要求子串表示的十进制数是 2019 的倍数。解法是利用同余定理将问题转化为“前缀和模 2019 的值相等的个数”本质也是值域统计模数范围固定为 2019。ARC 096-C Half and Half给定三种披萨的单价和组合价求买 A 个 A 类、B 个 B 类的最小花费。解法是枚举组合购买的数量因为组合数量不会超过min(A, B)而A, B ≤ 10⁵但枚举范围被约束在≤ 10⁵所以是 O(min(A,B))而非 O(A×B)。Codeforces Round #634 (Div. 3) E Array Shrinking区间 DP 题但优化点在于每个区间合并后的值不会超过log(max(a))所以 DP 状态可以按“右端点和值”来设计将复杂度从 O(N³) 降到 O(N² log N)。你会发现所有这些题的破局点都是识别出“某个维度的取值范围远小于输入规模”然后主动将算法重心从“处理 N 个元素”转移到“处理 M 个可能的值”。这是一种底层的算法直觉需要大量刷题来培养。最后一个小技巧在 AtCoder 上如果你的代码在本地测试通过但提交后 TLE90% 的原因是用了 Python 的input().split()而不是sys.stdin.readline().split()。后者快 5-10 倍。在 C 中记得关同步ios::sync_with_stdio(0); cin.tie(0);。这些 IO 优化往往是区分“AC”和“TLE”的最后一道门槛。