必须用二进制枚举是因为容斥原理需遍历全部 $2^n - 1$ 个非空子集，每位二进制数对应一个集合的选/不选，可系统、简洁、无遗漏地实现奇加偶减；手动写n层循环不可行，dfs易冗余，而二进制枚举时间复杂度o(2ⁿ)且代码紧凑。

容斥原理在 C++ 中结合二进制枚举实现，本质是用 int 的每一位代表一个集合是否被选中，从而系统性地遍历所有子集组合并按奇加偶减规则累加/减去交集大小。这不是“自动消除重叠”，而是靠数学公式 + 枚举覆盖所有重叠情形。

为什么必须用二进制枚举来实现容斥

容斥原理的展开形式是：
｜A₁ ∪ A₂ ∪ … ∪ Aₙ｜ = Σ｜Aᵢ｜ − Σ｜Aᵢ ∩ Aⱼ｜ + Σ｜Aᵢ ∩ Aⱼ ∩ Aₖ｜ − … + (−1)ⁿ⁺¹｜A₁ ∩ … ∩ Aₙ｜
手动写 n 层循环不现实，而 n 个集合的所有非空子集共 2ⁿ − 1 个——这恰好对应 0 到 (1 的整数二进制表示。

• 每个整数 i 的二进制位（如第 j 位为 1）表示“选中第 j 个集合”
• __builtin_popcount(i) 直接给出当前子集含几个集合，决定符号是 +1 还是 -1
• 交集计算逻辑需由你定义（比如求满足多个条件的整数个数、区间重叠长度等），不能依赖 STL 自动完成

典型代码结构：从枚举到符号控制

核心骨架固定，关键是把“交集大小”算准：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

int n = 3; // 假设 3 个条件集合 A0, A1, A2
long long ans = 0;
for (int mask = 1; mask 

• mask 从 1 开始（跳过空集），上限是 (1
• calc_intersection(mask) 必须根据实际问题实现，例如：求 [1, N] 中能被 mask 对应质数同时整除的数的个数 → 就是 N / lcm(这些质数)
• 若用 int 存 mask，n 最大建议 ≤ 20；超了得换 long long 或分治

常见翻车点：交集逻辑写错或溢出

最容易忽略的是交集计算本身引入的错误，和容斥无关，但会让结果全错：

• 多个数求 LCM 时没先除 GCD，导致中间结果溢出 —— 应写成 lcm(a, b) = a / gcd(a, b) * b，顺序不能反
• 条件之间实际不独立（比如 A₂ ⊆ A₁），但你仍按普通容斥硬套，会导致重复扣除 —— 此时要先去重或改用莫比乌斯反演
• 边界处理漏掉 0 或负数，比如算“≤ N 且满足条件”的个数，却用了 N / x 而没考虑 x > N 时结果应为 0
• 使用 __builtin_popcount 时传入负数（符号位干扰），务必 cast 成 unsigned 或用 bitset(mask).count()

真正难的从来不是枚举，而是对每个 mask 准确算出交集大小 —— 这一步没抽象清楚，二进制再漂亮也白搭。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！