C++容斥原理详解（从零开始掌握容斥原理算法与实战应用）

为什么需要C++实现容斥原理？

在编程竞赛（如ACM、蓝桥杯）或工程开发中，经常遇到这样的问题：

• 1 到 N 中能被 a 或 b 整除的数有多少个？
• 满足多个条件的排列组合数量？
• 求多个事件至少发生一个的概率？

这些问题都可以通过C++组合数学中的容斥原理高效解决。而C++因其高性能和位运算支持，成为实现该算法的理想语言。

容斥原理的通用公式

对于 n 个集合 S₁, S₂, ..., Sₙ，其并集大小为：

|S₁ ∪ S₂ ∪ ... ∪ Sₙ| = Σ|Sᵢ| - Σ|Sᵢ ∩ Sⱼ| + Σ|Sᵢ ∩ Sⱼ ∩ Sₖ| - ... + (-1)ⁿ⁺¹|S₁ ∩ S₂ ∩ ... ∩ Sₙ|

也就是说，我们需要枚举所有非空子集，并根据子集大小的奇偶性决定加或减。

C++实现容斥原理

我们以一个经典问题为例：求 1 到 N 中能被给定数组 nums 中任意一个数整除的整数个数。

例如：N = 100，nums = [2, 3, 5]，求 1~100 中能被 2、3 或 5 整除的数的个数。

思路：对 nums 的所有非空子集，计算其最小公倍数（LCM），然后用 N / LCM 得到能被该子集中所有数整除的数的个数。根据子集大小奇偶性加减。

以下是完整的C++代码实现：

#include <iostream>#include <vector>#include <numeric> // for std::lcm (C++17)using namespace std;// 如果编译器不支持 C++17，可手动实现 lcmlong long gcd(long long a, long long b) {    if (b == 0) return a;    return gcd(b, a % b);}long long lcm(long long a, long long b) {    return a / gcd(a, b) * b;}// 容斥原理主函数long long countDivisible(long long N, vector<long long>& nums) {    int n = nums.size();    long long total = 0;    // 枚举所有非空子集：从 1 到 (1 << n) - 1    for (int mask = 1; mask < (1 << n); ++mask) {        long long current_lcm = 1;        int cnt = 0; // 子集元素个数        for (int i = 0; i < n; ++i) {            if (mask & (1 << i)) {                current_lcm = lcm(current_lcm, nums[i]);                cnt++;                // 防止 lcm 溢出或超过 N                if (current_lcm > N) break;            }        }        if (current_lcm > N) continue;        if (cnt % 2 == 1) {            total += N / current_lcm;        } else {            total -= N / current_lcm;        }    }    return total;}int main() {    long long N = 100;    vector<long long> nums = {2, 3, 5};    cout << "1 到 " << N << " 中能被 2、3 或 5 整除的数有："         << countDivisible(N, nums) << " 个" << endl;    return 0;}

运行结果：

1 到 100 中能被 2、3 或 5 整除的数有：74 个

代码解析

• 位掩码枚举：使用整数 mask 从 1 到 2ⁿ−1 表示所有非空子集。
• LCM 计算：子集中所有数的最小公倍数决定了能同时被这些数整除的数的周期。
• 奇加偶减：子集大小为奇数时加，偶数时减，符合容斥原理。
• 溢出处理：若 LCM 超过 N，说明没有数能被整除，直接跳过。

应用场景扩展

容斥原理编程教程不仅限于整除问题，还可用于：

• 计算满足多个限制条件的排列数
• 求解概率问题（如至少一个事件发生）
• 图论中路径计数（排除非法路径）
• 动态规划状态去重

小结

通过本文，你已经掌握了C++容斥原理的基本思想、数学公式和代码实现。只要理解“加减交替、枚举子集”的核心逻辑，就能灵活应对各类计数难题。建议多练习类似题目（如 LeetCode 804、Codeforces 容斥专题），巩固所学知识。

记住：**容斥原理算法**不是魔法，而是逻辑清晰的数学工具。用好它，你的算法能力将更上一层楼！