企业官网建设流程全解析

1. 题目到底在问什么：从“找倍数”到“算集合覆盖”

先说这道题本身。给定一个整数 n 和一个集合 S（集合里有 m 个整数），要求统计 1 到 n-1 之间，有多少个数至少能被 S 中某一个数整除。

我第一次看到这个题目的时候，脑子里冒出来的解法特别直白：从 1 循环到 n-1，对每个数判断它能否被集合里的任何一个数整除，能就计数器加一。这个思路完全正确，但问题在于 n 可以大到 2^31 这个量级。真要按这个思路写，哪怕集合里只有一个 2，也要循环二十亿次，更别说还要对每个数做 m 次取模判断，在当前绝大多数评测环境下，妥妥的超时，根本没得商量。

所以这道题的核心矛盾在于：你的答案需要覆盖一个巨大的区间，但你真正能用到的信息只有集合 S 的整除关系。如果要硬遍历，复杂度是 O(n * m)，而 n 是大到上亿甚至更多的量级，这显然不是出题人想让你走的路。

换个角度想：我们其实不是在“数数”，而是在算一种覆盖关系——集合 S 里的每个元素都能“罩住”区间里的一批数（它的倍数），而我们要算的是所有元素罩住的那些数加在一起到底有多大。

这样一来问题就变了：每个元素所影响的倍数集合是清晰可算的——区间内能被 x 整除的数的个数就是 floor((n-1) / x)。麻烦的只是这些集合之间有重叠，而且重叠的部分不是一两层，可能是多个元素同时覆盖同一个数。如果直接把这些集合大小加起来，一定会有重复计算的部分，而且重复的层数还不一样，不能靠简单剪一刀来解决。

这就要引出我们处理“多个条件至少满足一个”这类计数问题的标准武器——容斥原理。它的核心作用正是回答：几个集合的并集到底有多大？已知每个集合的大小，以及任意多个集合的交集大小，能不能把并集精确算出来？

2. 容斥原理的几何直觉：为什么会多算，又怎么把多算的补回来

容斥原理的公式大家大概都见过：

|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

但很多人只是背了公式，并不知道它背后的逻辑。我习惯用一个比较直观的方式来理解：假设有三个人各拿了一块布在地上铺，每块布代表一个集合，你要算的是三块布遮住的地面总面积。一个人铺的时候，新布落下去，总会和已经铺好的布产生重叠。你要是直接把三块布的面积相加，重叠部分就被算了两次。于是你打算把两两重叠的区域减掉一次，让重叠区域只算一次。可是当你减掉所有两两重叠的区域之后，三块布共同盖住的那一小块地方——它本来在三块布的每一块里都出现过，也就是说在总和里被算了三次——被你减了三次，直接减没了，地面反而漏了一个洞。所以最后必须把三块布都盖住的那块再加回来一次。

理解了这层关系，容斥的形态就呼之欲出：奇数个集合的交集加上，偶数个集合的交集减去。

套到我们这个问题上，被 S 中某些数同时整除，就是这个集合交集。用数学语言说：

设 S = {a1, a2, ..., am}，对于任意非空子集 T ⊆ S，定义：

f(T) = floor((n-1) / lcm(T))

这里 lcm(T) 表示 T 中所有数的最小公倍数。一个数能被 T 里所有数同时整除，当且仅当它能被 lcm(T) 整除。所以 f(T) 算出的就是区间里“同时被 T 中所有数整除”的数的数量。

最终的答案就是：

答案 = Σ (-1)^(|T|+1) * f(T) ，对所有非空子集 T

|T| 为奇数时 (-1)^(|T|+1) 是 +1，为偶数时是 -1，正好对应上面的结论。

这里顺便解释一个常见的疑问：为什么求交集的大小要用 lcm 而不是直接乘起来？因为 S 里的数不互质。比如 6 和 10，它们的最小公倍数是 30，不是 60。如果一个数是 6 的倍数也是 10 的倍数，那它一定是 30 的倍数；只有 60 的倍数这个条件就筛掉了一半原本合法的数，答案就会偏小。所以凡是涉及“同时被多个数整除”的计数，一律先求最小公倍数再取整，这是一个很基础的细节，但也是新手最容易出错的地方。

继续往深处想一步：如果我们不依赖公式，手工推两个集合的情况做验证。假设 S = {2, 3}，n = 11，区间是 1 到 10。

• 2 的倍数：2, 4, 6, 8, 10，共 5 个
• 3 的倍数：3, 6, 9，共 3 个
• 直接相加是 8，但 6 被算了两次，真实答案应该是 7

用容斥公式：5 + 3 - floor(10 / lcm(2,3)=6) = 5 + 3 - 1 = 7。完全吻合。

这就是整个思路的全部核心了。剩下的问题只有一个：怎么在代码里枚举 S 的所有非空子集，并且快速算出每个子集的 lcm。

3. 位掩码暴力枚举子集：为什么 m=10 的规模正好合适

这个问题里的 m（集合中元素个数）通常不会很大，经典数据范围是 m ≤ 10，这就是为什么标题里加了“暴力”两个字——直接用位掩码枚举所有子集，2^10 = 1024 种情况，完全不担心性能。

我见过不少人在这个地方绕了远路：有的写递归去枚举组合，有的用队列维护状态，其实都没必要。对于集合人数很少的情况，二进制位掩码是最自然的方式。把每个元素对应到二进制的一位：第 i 位为 1 表示该元素在子集中，为 0 表示不在。这样从 1 循环到 (1<<m)-1，就覆盖了所有非空子集。

核心代码如下：

#include <bits/stdc++.h> using namespace std; long long gcd(long long a, long long b) { while (b) { long long t = a % b; a = b; b = t; } return a; } long long lcm(long long a, long long b) { // 注意顺序：先除后乘，防止中间结果溢出 return a / gcd(a, b) * b; } int main() { long long n; int m; while (cin >> n >> m) { vector<long long> a; for (int i = 0; i < m; i++) { long long x; cin >> x; if (x > 0) a.push_back(x); // 跳过 0，原因见下一节 } m = a.size(); long long ans = 0; for (int mask = 1; mask < (1 << m); mask++) { long long cur = 1; int bits = 0; for (int i = 0; i < m; i++) { if (mask & (1 << i)) { cur = lcm(cur, a[i]); bits++; // 剪枝：当前 lcm 已经超过区间上限，后面不用算了 if (cur > n - 1) break; } } if (cur > n - 1) continue; if (bits & 1) ans += (n - 1) / cur; else ans -= (n - 1) / cur; } cout << ans << "\n"; } return 0; }

这个代码看起来短，但每一行都有讲究。mask & (1 << i)用来判断第 i 个元素是否在当前子集中；bits记录当前子集的大小，用来决定该加还是该减；cur从 1 开始不断取当前已选元素的 lcm，也就是这个子集的 lcm。

关于枚举的顺序，我习惯从mask = 1开始而不是从 0 开始，因为空集在容斥公式里没有任何贡献，从 1 开始可以天然跳过它。当然你从 0 写、在循环体内特判掉也行，但没必要多写一个分支。

两个小的性能优化，在 m=10 的时候可能体现不出来，但值得养成习惯：

• 如果当前子集的 lcm 已经大于 n-1，那么无论再并多少元素进去，lcm 只会更大不会变小。此时(n-1)/cur一定为 0，可以直接剪枝。
• 读入集合的时候就先把 0 和负数过滤掉，避免后续每次 lcm 都要特判。

你可能会问：为什么要用(1 << m)？因为 2^m 恰好等于长度为 m 的二进制序列的总个数。每一位有两种取值：选或不选。m=10 时只有 1024 种，暴力枚举完全可接受；m 到 20 左右的时候是 104 万种，属于“稍微压一压还能过”的水平；m 超过 25 就要考虑折半枚举或 DP 优化了，单纯暴力就力不从心了。

4. 真正卡住人的地方：lcm 三大坑与 0 值陷阱

如果只是照着模板抄一遍代码，你可能一次就过了。但如果你是自己从零开始想，前面至少有三四个坑排着队等你踩。我把自己当初挨个踩过一遍的经验整理在这里，希望你能少走这段弯路。

4.1 集合里有 0：第一行代码就要处理

题目给的输入并不保证集合里全是正整数，原题的数据里就可能有 0。0 不能做除数，lcm(x, 0)在数学上也没有定义，所以这个数必须在读入阶段就过滤掉，否则在cur = lcm(cur, 0)这一步就会得到错误结果或者运行时异常。

还有一个容易忽略的情况：集合里可能混入负数。负数的倍数和正数的倍数在“能被整除”这件事上完全等价（-4 的倍数集合和 4 的倍数集合一样），所以统一只保留正数就对了。我在代码里用一个if (x > 0)就把这两种情况一并处理了。不要用x != 0，因为负数后面还是会给你带来无穷无尽的麻烦。

4.2 lcm 的溢出：先除后乘，不是先乘后除

看着lcm(a, b) = a / gcd(a, b) * b这个式子，好像和a * b / gcd(a, b)差不多，但两个写法在实际运行中差别巨大。

n 的最大值在这个题里可以到 2^31 附近，集合里的数也可能是接近这个量级的数。如果先做a * b，两个 10 位数相乘，结果轻松突破 64 位整数的范围，直接溢出变成负数或者一个错得离谱的数。而先做除法，把 a 和 b 的公因子消掉一部分，再做乘法，中间结果就能稳稳落在安全范围内。

举个例子：a = 2^30，b = 3 * 2^20。先算 ab 是约 3 * 2^50，已经溢出；先除 gcd(2^30, 32^20) = 2^20，变成2^10 * 3 * 2^20 = 3 * 2^30，这一点都不越界。这不是什么高级技巧，就是最最基本的“防溢出顺序”，但我在实际刷题和帮别人看代码的时候，发现有一半的 lcm 相关错误都出在这一个顺序上。

我在写 lcm 函数时全部参数和返回值都用long long，这也是必须的。如果你在这里用了int，n 很大时连存都存不下，谈什么正确性。

4.3 数据重复：不去重，答案就会错得莫名其妙

如果输入集合里同时出现 2 和 4，会发生什么？2 的倍数集合是 4 的倍数集合的超集。两层的容斥会先加上 2 的倍数集合，再加上 4 的倍数集合，再减掉 2 和 4 的 lcm（也就是 4）的倍数集合。看起来好像绕了一圈又绕回来了，但实际上仍然是对的。

真正会出问题的情况是：集合里有多个相等的数。比如 {2, 2, 3}。这时 2 和另一个 2 的“交集”实际上就是 2 的倍数集合，容斥公式里会出现“同一个集合重复参与奇偶计算”的局面，最后答案偏大或者偏小，而且偏差值很隐蔽，不是一眼能看出来的那种。

所以稳妥的做法是读入后先去重。上面的代码里我没写去重那两行，是因为题面通常默认集合元素互不相同。但既然这里提出来了，我建议大家在自己的代码里加一个sort加unique的操作，不过几十微秒的事，换来的是心里踏实。

sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end());

4.4 验证：拿样例和手推结果对一遍

拿到代码之后，千万不要直接交。用一个很小的数据手动验证一下。比如：

输入：

10 2 2 3

期望答案：区间 1 到 9，能被 2 或 3 整除的数有 2, 3, 4, 6, 8, 9，共 6 个。

再比如：

10 3 2 4 5

2 的倍数 4 个，4 的倍数 2 个，5 的倍数 1 个。两两交集：lcm(2,4)=4 是 2 的倍数有 2 个，lcm(2,5)=10 超界为 0，lcm(4,5)=20 超界为 0；三交集 lcm(2,4,5)=20 超界为 0。所以答案是 4+2+1-2-0-0+0 = 5。实际列出来：2, 4, 5, 6, 8，确实是 5。用这种小数据验证，代码里任何符号错误都能暴露出来。

5. 从这道题延伸出去：容斥与暴力枚举还能解决哪些问题

很多人把这道题当成一个孤立的模板题，背完就忘。但实际上它的思想可以迁移到不少别的场景，而且迁移的路径非常清晰。

5.1 复杂度与规模边界

先把这个题本身的复杂度说透：位掩码枚举是 2^m 个子集，计算每个子集的 lcm 平均需要 O(m) 次 gcd，单次 gcd 是 O(log C)，C 是数值范围。所以总复杂度大约是 O(2^m * m * log n)。m=10 时约 1 万次 gcd 计算，随便跑；m=15 时约 50 万次，仍然轻松；m=20 时约 2000 万次，开始有点压力但优化后能过；m=25 以上，纯暴力就有点悬了。我自己在实际项目中会以 m=20 作为一个“还能暴力”的心理界线，超过这个数就去想别的办法。

5.2 迁移场景：区间问题、错排、同余方程

容斥原理最常见的迁移场景是“区间内满足若干条件中至少一个的计数”。这类题的核心都是同一个套路：把“满足至少一个”转化为“所有单集合之和减去两两交集加上三交集……”。例如给定若干质数，求 1 到 n 中不被任何一个质数整除的数有几个——这个问题和原题本质上没有区别，只是最后答案做个减法。还有给定若干同余条件，求满足任意一个条件的数的个数，同样可以套容斥。

另外一类经典应用是错排问题：求所有排列中没有任何一个元素留在原位的排列数。看上去和集合覆盖没有关系，但你把“第 i 个元素留在原位”看成一个事件，要求“这些事件全都不发生”，就是容斥在做的事。这类问题在离散数学和组合计数里经常出现，从这道题打底，再去理解错排公式会顺畅得多。

再有一个实际工程里也能遇到的场景：定时任务调度。假设系统里有几个周期任务，周期分别为 p1, p2, ..., pm，你想知道在某个时间区间内“至少有一个任务会触发”的时刻有多少个。这本质上就是求这几个倍数集合的并集大小，和这道题一模一样。只不过工程里的 m 一般不大，容斥的枚举开销完全可以接受。

5.3 进阶：m 很大的时候怎么办

如果你刷题时遇到一个加强版，m 变成了 30 怎么办？纯枚枚举 2^30 是 10 亿级别，肯定不行。这时候常见的思路是折半枚举（Meet in the Middle）：把集合拆成两半，分别枚举两半的所有子集和对应 lcm，然后用某种方式合并两半的结果——比如对一堆超大 lcm 做贪心或排序加双指针。这个做法在这里不太好直接套，因为 lcm 是非线性的，合并时需要额外处理互质条件，比较复杂。

另一个更实用的思路是：如果一个数能被集合里另一个数整除，它其实根本不需要参与容斥。比如集合里同时有 2 和 6，任何一个能被 6 整除的数必然能被 2 整除，那么 6 在集合里是冗余的，可以直接删掉。做完这种“倍数约简”之后，集合大小往往能显著下降，很多 m=30 的极限数据就能被压到暴力可解的范围。这个优化在原题里不一定用得上，但遇到加强版数据时可以救命。

我之前在某次练习赛里真的吃过这个亏：m=24，没有做倍数约简，暴力跑了 1600 多万个状态，勉强卡在时限边缘。后来加了约简，有效集合直接缩到 10 个左右，速度提升了一个数量级。所以这个技巧值得记下来。

6. 写这题的五个经验总结

写了这么多，最后用几条零碎但实在的经验收个尾吧，都是我在反复写这类题之后沉淀下来的东西。

第一，遇到“至少一个”相关的计数问题，第一反应不应该是去遍历所有元素然后逐一判断，而是想想能不能用容斥把问题转换成“并集大小”的计算。前者往往复杂度不可接受，后者往往有漂亮的多项式解。

第二，最小公倍数相关的计算，务必把a / gcd(a, b) * b当成肌肉记忆，而不是a * b / gcd(a, b)。这个顺序问题可能在十道题里九道都不爆，但一旦遇到大数据，代价就是一次无谓的 Wrong Answer。

第三，子集枚举用位掩码就好，不要写递归。递归本身不复杂，但维护状态、回溯、收集结果这些步骤会引入额外的出错点。位掩码直接把“选哪些元素”编码成一个整数，代码短，调试也容易。

第四，写完了先弄一组小数据手算验证，再交。小数据验证成本极低，但能抓出容斥符号反了、lcm 公式写错、边界条件漏了等好多问题。

第五，学会把一道题的解法抽象出来。容斥加位掩码这套组合，完全不是只能用在“求能被几个数整除”的问题上——只要问题里有一组条件、要算这些条件的并集，这套思路就还能用。带着这种眼光刷题，一百道题就能顶别人五百道。

这道题给我最大的收获倒不是容斥公式本身，而是“把复杂问题拆成可枚举的小问题”这个思路。所谓暴力，不是真的无脑遍历所有可能，而是把问题规模压到能暴力解决的量级之后，再把这份暴力写到极致。 ## 1. 题目到底在问什么：从“找倍数”到“算集合覆盖”

先说这道题本身。给定一个整数 n 和一个集合 S（集合里有 m 个整数），要求统计 1 到 n-1 之间，有多少个数至少能被 S 中某一个数整除。

我第一次看到这个题目的时候，脑子里冒出来的解法特别直白：从 1 循环到 n-1，对每个数判断它能否被集合里的任何一个数整除，能就计数器加一。这个思路完全正确，但问题在于 n 可以大到 2^31 这个量级。真要按这个思路写，哪怕集合里只有一个 2，也要循环二十亿次，更别说还要对每个数做 m 次取模判断，在当前绝大多数评测环境下，妥妥的超时，根本没得商量。

所以这道题的核心矛盾在于：你的答案需要覆盖一个巨大的区间，但你真正能用到的信息只有集合 S 的整除关系。如果要硬遍历，复杂度是 O(n * m)，而 n 是大到上亿甚至更多的量级，这显然不是出题人想让你走的路。

换个角度想：我们其实不是在“数数”，而是在算一种覆盖关系——集合 S 里的每个元素都能“罩住”区间里的一批数（它的倍数），而我们要算的是所有元素罩住的那些数加在一起到底有多大。

这样一来问题就变了：每个元素所影响的倍数集合是清晰可算的——区间内能被 x 整除的数的个数就是 floor((n-1) / x)。麻烦的只是这些集合之间有重叠，而且重叠的部分不是一两层，可能是多个元素同时覆盖同一个数。如果直接把这些集合大小加起来，一定会有重复计算的部分，而且重复的层数还不一样，不能靠简单剪一刀来解决。

这就要引出我们处理“多个条件至少满足一个”这类计数问题的标准武器——容斥原理。它的核心作用正是回答：几个集合的并集到底有多大？已知每个集合的大小，以及任意多个集合的交集大小，能不能把并集精确算出来？

2. 容斥原理的几何直觉：为什么会多算，又怎么把多算的补回来

容斥原理的公式大家大概都见过：

|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

但很多人只是背了公式，并不知道它背后的逻辑。我习惯用一个比较直观的方式来理解：假设有三个人各拿了一块布在地上铺，每块布代表一个集合，你要算的是三块布遮住的地面总面积。一个人铺的时候，新布落下去，总会和已经铺好的布产生重叠。你要是直接把三块布的面积相加，重叠部分就被算了两次。于是你打算把两两重叠的区域减掉一次，让重叠区域只算一次。可是当你减掉所有两两重叠的区域之后，三块布共同盖住的那一小块地方——它本来在三块布的每一块里都出现过，也就是说在总和里被算了三次——被你减了三次，直接减没了，地面反而漏了一个洞。所以最后必须把三块布都盖住的那块再加回来一次。

理解了这层关系，容斥的形态就呼之欲出：奇数个集合的交集加上，偶数个集合的交集减去。

套到我们这个问题上，被 S 中某些数同时整除，就是这个集合交集。用数学语言说：

设 S = {a1, a2, ..., am}，对于任意非空子集 T ⊆ S，定义：

f(T) = floor((n-1) / lcm(T))

这里 lcm(T) 表示 T 中所有数的最小公倍数。一个数能被 T 里所有数同时整除，当且仅当它能被 lcm(T) 整除。所以 f(T) 算出的就是区间里“同时被 T 中所有数整除”的数的数量。

最终的答案就是：

答案 = Σ (-1)^(|T|+1) * f(T) ，对所有非空子集 T

|T| 为奇数时 (-1)^(|T|+1) 是 +1，为偶数时是 -1，正好对应上面的结论。

这里顺便解释一个常见的疑问：为什么求交集的大小要用 lcm 而不是直接乘起来？因为 S 里的数不互质。比如 6 和 10，它们的最小公倍数是 30，不是 60。如果一个数是 6 的倍数也是 10 的倍数，那它一定是 30 的倍数；只有 60 的倍数这个条件就筛掉了一半原本合法的数，答案就会偏小。所以凡是涉及“同时被多个数整除”的计数，一律先求最小公倍数再取整，这是一个很基础的细节，但也是新手最容易出错的地方。

继续往深处想一步：如果我们不依赖公式，手工推两个集合的情况做验证。假设 S = {2, 3}，n = 11，区间是 1 到 10。

• 2 的倍数：2, 4, 6, 8, 10，共 5 个
• 3 的倍数：3, 6, 9，共 3 个
• 直接相加是 8，但 6 被算了两次，真实答案应该是 7

用容斥公式：5 + 3 - floor(10 / lcm(2,3)=6) = 5 + 3 - 1 = 7。完全吻合。

这就是整个思路的全部核心了。剩下的问题只有一个：怎么在代码里枚举 S 的所有非空子集，并且快速算出每个子集的 lcm。

3. 位掩码暴力枚举子集：为什么 m=10 的规模正好合适

这个问题里的 m（集合中元素个数）通常不会很大，经典数据范围是 m ≤ 10，这就是为什么标题里加了“暴力”两个字——直接用位掩码枚举所有子集，2^10 = 1024 种情况，完全不担心性能。

我见过不少人在这个地方绕了远路：有的写递归去枚举组合，有的用队列维护状态，其实都没必要。对于集合人数很少的情况，二进制位掩码是最自然的方式。把每个元素对应到二进制的一位：第 i 位为 1 表示该元素在子集中，为 0 表示不在。这样从 1 循环到 (1<<m)-1，就覆盖了所有非空子集。

核心代码如下：

#include <bits/stdc++.h> using namespace std; long long gcd(long long a, long long b) { while (b) { long long t = a % b; a = b; b = t; } return a; } long long lcm(long long a, long long b) { // 注意顺序：先除后乘，防止中间结果溢出 return a / gcd(a, b) * b; } int main() { long long n; int m; while (cin >> n >> m) { vector<long long> a; for (int i = 0; i < m; i++) { long long x; cin >> x; if (x > 0) a.push_back(x); // 跳过 0，原因见下一节 } m = a.size(); long long ans = 0; for (int mask = 1; mask < (1 << m); mask++) { long long cur = 1; int bits = 0; for (int i = 0; i < m; i++) { if (mask & (1 << i)) { cur = lcm(cur, a[i]); bits++; // 剪枝：当前 lcm 已经超过区间上限，后面不用算了 if (cur > n - 1) break; } } if (cur > n - 1) continue; if (bits & 1) ans += (n - 1) / cur; else ans -= (n - 1) / cur; } cout << ans << "\n"; } return 0; }

这个代码看起来短，但每一行都有讲究。mask & (1 << i)用来判断第 i 个元素是否在当前子集中；bits记录当前子集的大小，用来决定该加还是该减；cur从 1 开始不断取当前已选元素的 lcm，也就是这个子集的 lcm。

关于枚举的顺序，我习惯从mask = 1开始而不是从 0 开始，因为空集在容斥公式里没有任何贡献，从 1 开始可以天然跳过它。当然你从 0 写、在循环体内特判掉也行，但没必要多写一个分支。

两个小的性能优化，在 m=10 的时候可能体现不出来，但值得养成习惯：

• 如果当前子集的 lcm 已经大于 n-1，那么无论再并多少元素进去，lcm 只会更大不会变小。此时(n-1)/cur一定为 0，可以直接剪枝。
• 读入集合的时候就先把 0 和负数过滤掉，避免后续每次 lcm 都要特判。

你可能会问：为什么要用(1 << m)？因为 2^m 恰好等于长度为 m 的二进制序列的总个数。每一位有两种取值：选或不选。m=10 时只有 1024 种，暴力枚举完全可接受；m 到 20 左右的时候是 104 万种，属于“稍微压一压还能过”的水平；m 超过 25 就要考虑折半枚举或 DP 优化了，单纯暴力就力不从心了。

4. 真正卡住人的地方：lcm 三大坑与 0 值陷阱

如果只是照着模板抄一遍代码，你可能一次就过了。但如果你是自己从零开始想，前面至少有三四个坑等着你踩。我把自己当初挨个踩过一遍的经验整理在这里，希望你能少走这段弯路。

4.1 集合里有 0：第一行代码就要处理

题目给的输入并不保证集合里全是正整数，原题的数据里就可能有 0。0 不能做除数，lcm(x, 0) 在数学上也没有定义，所以这个数必须在读入阶段就过滤掉，否则在 cur = lcm(cur, 0) 这一步就会得到错误结果或者运行时异常。

还有一个容易忽略的情况：集合里可能混入负数。负数的倍数和正数的倍数在“能被整除”这件事上完全等价（-4 的倍数集合和 4 的倍数集合一样），所以统一只保留正数就对了。我在代码里用一个if (x > 0)就把这两种情况一并处理了。不要用x != 0，因为负数后面还是会给你带来无穷无尽的麻烦。

4.2 lcm 的溢出：先除后乘，不是先乘后除

看着lcm(a, b) = a / gcd(a, b) * b这个式子，好像和a * b / gcd(a, b)差不多，但两个写法在实际运行中差别巨大。

n 的最大值在这个题里可以到 2^31 附近，集合里的数也可能是接近这个量级的数。如果先做a * b，两个 10 位数相乘，结果轻松突破 64 位整数的范围，直接溢出变成负数或者一个错得离谱的数。而先做除法，把 a 和 b 的公因子消掉一部分，再做乘法，中间结果就能稳稳落在安全范围内。

举个例子：a = 2^30，b = 3 * 2^20。先算 ab 是约 3 * 2^50，已经溢出；先除 gcd(2^30, 32^20) = 2^20，变成 2^10 * 3 * 2^20 = 3 * 2^30，这一点都不越界。这不是什么高级技巧，就是最最基本的“防溢出顺序”，但我在实际刷题和帮别人看代码的时候，发现有一半的 lcm 相关错误都出在这一个顺序上。

我在写 lcm 函数时全部参数和返回值都用long long，这也是必须的。如果你在这里用了int，n 很大时连存都存不下，谈什么正确性。

4.3 数据重复：不去重，答案就会错得莫名其妙

如果输入集合里同时出现 2 和 4，会发生什么？2 的倍数集合是 4 的倍数集合的超集。两层的容斥会先加上 2 的倍数集合，再加上 4 的倍数集合，再减掉 2 和 4 的 lcm（也就是 4）的倍数集合。看起来好像绕了一圈又绕回来了，但实际上仍然是对的。

真正会出问题的情况是：集合里有多个相等的数。比如 {2, 2, 3}。这时 2 和另一个 2 的“交集”实际上就是 2 的倍数集合，容斥公式里会出现“同一个集合重复参与奇偶计算”的局面，最后答案偏大或者偏小，而且偏差值很隐蔽，不是一眼能看出来的那种。

所以稳妥的做法是读入后先去重。上面的代码里我没写去重那两行，是因为题面通常默认集合元素互不相同。但既然这里提出来了，我建议大家在自己的代码里加一个sort加unique的操作，不过几十微秒的事，换来的是心里踏实。

sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end());

4.4 验证：拿样例和手推结果对一遍

拿到代码之后，千万不要直接交。用一个很小的数据手动验证一下。比如：

输入：

10 2 2 3

期望答案：区间 1 到 9，能被 2 或 3 整除的数有 2, 3, 4, 6, 8, 9，共 6 个。

再比如：

10 3 2 4 5

2 的倍数 4 个，4 的倍数 2 个，5 的倍数 1 个。两两交集：lcm(2,4)=4 是 2 的倍数有 2 个，lcm(2,5)=10 超界为 0，lcm(4,5)=20 超界为 0；三交集 lcm(2,4,5)=20 超界为 0。所以答案是 4+2+1-2-0-0+0 = 5。实际列出来：2, 4, 5, 6, 8，确实是 5。用这种小数据验证，代码里任何符号错误都能暴露出来。

5. 从这道题延伸出去：容斥与暴力枚举还能解决哪些问题

很多人把这道题当成一个孤立的模板题，背完就忘。但实际上它的思想可以迁移到不少别的场景，而且迁移的路径非常清晰。

5.1 复杂度与规模边界

先把这个题本身的复杂度说透：位掩码枚举是 2^m 个子集，计算每个子集的 lcm 平均需要 O(m) 次 gcd，单次 gcd 是 O(log C)，C 是数值范围。所以总复杂度大约是 O(2^m * m * log n)。m=10 时约 1 万次 gcd 计算，随便跑；m=15 时约 50 万次，仍然轻松；m=20 时约 2000 万次，开始有点压力但优化后能过；m=25 以上，纯暴力就有点悬了。我自己在实际项目中会以 m=20 作为一个“还能暴力”的心理界线，超过这个数就去想别的办法。

5.2 迁移场景：区间问题、错排、同余方程

容斥原理最常见的迁移场景是“区间内满足若干条件中至少一个的计数”。这类题的核心都是同一个套路：把“满足至少一个”转化为“所有单集合之和减去两两交集加上三交集……”。例如给定若干质数，求 1 到 n 中不被任何一个质数整除的数有几个——这个问题和原题本质上没有区别，只是最后答案做个减法。还有给定若干同余条件，求满足任意一个条件的数的个数，同样可以套容斥。

另外一类经典应用是错排问题：求所有排列中没有任何一个元素留在原位的排列数。看上去和集合覆盖没有关系，但你把“第 i 个元素留在原位”看成一个事件，要求“这些事件全都不发生”，就是容斥在做的事。这类问题在离散数学和组合计数里经常出现，从这道题打底，再去理解错排公式会顺畅得多。

再有一个实际工程里也能遇到的场景：定时任务调度。假设系统里有几个周期任务，周期分别为 p1, p2, ..., pm，你想知道在某个时间区间内“至少有一个任务会触发”的时刻有多少个。这本质上就是求这几个倍数集合的并集大小，和这道题一模一样。只不过工程里的 m 一般不大，容斥的枚举开销完全可以接受。

5.3 进阶：m 很大的时候怎么办

如果你刷题时遇到一个加强版，m 变成了 30 怎么办？纯枚枚举 2^30 是 10 亿级别，肯定不行。这时候常见的思路是折半枚举：把集合拆成两半，分别枚举两半的所有子集和对应 lcm，然后用某种方式合并两半的结果——比如对一堆超大 lcm 做贪心或排序加双指针。这个做法在这里不太好直接套，因为 lcm 是非线性的，合并时需要额外处理互质条件，比较复杂。

另一个更实用的思路是：如果一个数能被集合里另一个数整除，它其实根本不需要参与容斥。比如集合里同时有 2 和 6，任何一个能被 6 整除的数必然能被 2 整除，那么 6 在集合里是冗余的，可以直接删掉。做完这种“倍数约简”之后，集合大小往往能显著下降，很多 m=30 的极限数据就能被压到暴力可解的范围。这个优化在原题里不一定用得上，但遇到加强版数据时可以救命。

我之前在某次练习赛里真的吃过这个亏：m=24，没有做倍数约简，暴力跑了 1600 多万个状态，勉强卡在时限边缘。后来加了约简，有效集合直接缩到 10 个左右，速度提升了一个数量级。所以这个技巧值得记下来。

6. 写这题的几个经验总结

写了这么多，最后用几条零碎但实在的经验收个尾吧，都是我在反复写这类题之后沉淀下来的东西。

第一，遇到“至少一个”相关的计数问题，第一反应不应该是去遍历所有元素然后逐一判断，而是想想能不能用容斥把问题转换成“并集大小”的计算。前者往往复杂度不可接受，后者往往有漂亮的多项式解。

第二，最小公倍数相关的计算，务必把a / gcd(a, b) * b当成肌肉记忆，而不是a * b / gcd(a, b)。这个顺序问题可能在十道题里九道都不爆，但一旦遇到大数据，代价就是一次无谓的错误答案。

第三，子集枚举用位掩码就好，不要写递归。递归本身不复杂，但维护状态、回溯、收集结果这些步骤会引入额外的出错点。位掩码直接把“选哪些元素”编码成一个整数，代码短，调试也容易。

第四，写完了先弄一组小数据手算验证，再交。小数据验证成本极低，但能抓出容斥符号反了、lcm 公式写错、边界条件漏了等好多问题。

第五，学会把一道题的解法抽象出来。容斥加位掩码这套组合，完全不是只能用在“求能被几个数整除”的问题上——只要问题里有一组条件、要算这些条件的并集，这套思路就还能用。带着这种眼光刷题，一百道题就能顶别人五百道。

这道题给我最大的收获倒不是容斥公式本身，而是“把复杂问题拆成可枚举的小问题”这个思路。所谓暴力，不是真的无脑遍历所有可能，而是把问题规模压到能暴力解决的量级之后，再把这份暴力写到极致。