容斥原理：解决“至少一个”问题的神奇工具

你有没有遇到过这种情况：班级里统计喜欢数学、语文、英语的人数，老师想知道至少喜欢一门课的同学有多少。如果直接加总，肯定有人被重复算了——那些同时喜欢两门或三门课的同学。这时候，我们就需要 容斥原理（Inclusion-Exclusion Principle）来帮我们准确计数。简单说，容斥原理就是：先加所有单个集合，再减去重复的，最后加回多减的。它适用于计算多个集合的并集元素个数，或者解决“至少满足一个条件”的问题。

1. 先看两个集合的情况 —— 直观又简单

假设班上有 20 人喜欢数学，15 人喜欢语文，同时喜欢两门的有 5 人。那么至少喜欢一门的人数是多少？

如果我们直接加：20 + 15 = 35，但中间有 5 人被算了两次（既在数学组又在语文组）。正确的做法是减去这重复的 5 人：

|喜欢数学 ∪ 喜欢语文| = 20 + 15 - 5 = 30 人

这就是两个集合的容斥公式：

|A \cup B| = |A| + |B| - |A \cap B|

另一个生活例子：你妈妈给了你 10 元零花钱（集合 A），爸爸给了你 8 元（集合 B）。如果两人都给了你 3 元（两人重叠的部分，比如他们商量好各出 3 元买生日礼物），那你实际拿到手的钱 = 10 + 8 - 3 = 15 元。如果不减去重叠部分，你会以为自己有 18 元，但实际只有 15 元。

2. 三个集合的情况 —— 先加后减再补

当条件增加到三个时，公式变成：

|A \cup B \cup C| = (|A|+|B|+|C|) - (|A\cap B|+|A\cap C|+|B\cap C|) + |A\cap B\cap C|

为什么最后要加回三个集合的交集？因为一开始加单个时，三个交集的元素被加了 3 次；减去两两交集时，三个交集的元素又被减了 3 次，相当于被减没了，所以最后要加回来一次。

生活例子：老师调查三个兴趣班：数学（30人报名）、语文（25人）、英语（20人）。统计结果：

数学和语文都报名的：10人
数学和英语都报名的：8人
语文和英语都报名的：6人
三科都报名的：3人

那么至少报一科的人数 = (30+25+20) - (10+8+6) + 3 = 75 - 24 + 3 = 54 人。

思考题：如果三科都报名的有 0 人，那么结果就是 75 - 24 = 51 人，合理。

3. 一般形式：任意 n 个集合的通用公式

容斥原理可以推广到任意多个集合。公式像一个交替的加减号序列：

\left|\bigcup_{i=1}^n A_i\right| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_n|

先加所有单个集合
减去所有两两交集
加上所有三个交集
减去所有四个交集
……
最后根据集合个数 n 的奇偶决定符号：奇数个集合的项为正，偶数个集合的项为负。

在编程中，我们通常用 二进制枚举所有非空子集 来实现这个公式：用一个整数 mask 的二进制位表示每个集合是否被选中，然后根据选中的集合个数 bits 来决定是加还是减。

4. 编程应用：求能被多个数整除的个数

经典问题：求 1 到 N 中，能被 a、b 或 c 至少一个整除的数的个数。这等价于三个集合的并集：

A = {能被 a 整除的数}
B = {能被 b 整除的数}
C = {能被 c 整除的数}

4.1 三个固定除数的直接实现

如果除数只有三个且你知道它们互质（或愿意手动算 lcm），可以直接套公式。注意：两个数的 最小公倍数 (lcm) 才是真正表示“同时能被两者整除”的条件，不能简单用乘积，除非它们互质。但为了演示容斥思想，下面的代码假设除数两两互质（实际更严谨的做法见通用版本）。

C++ 代码（简化版）

#include <iostream>
using namespace std;

// 计算1到N中能被a或b或c至少一个整除的个数（假设备数互质）
int count_divisible(int N, int a, int b, int c) {
    int cnt_a = N / a;          // 能被a整除的个数
    int cnt_b = N / b;          // 能被b整除的个数
    int cnt_c = N / c;          // 能被c整除的个数
    int cnt_ab = N / (a * b);   // 同时被a和b整除（这里直接用乘积，实际需lcm）
    int cnt_ac = N / (a * c);   // 同时被a和c整除
    int cnt_bc = N / (b * c);   // 同时被b和c整除
    int cnt_abc = N / (a * b * c); // 同时被a,b,c整除
    // 容斥公式：加单个，减两两，加三重
    return cnt_a + cnt_b + cnt_c - cnt_ab - cnt_ac - cnt_bc + cnt_abc;
}

int main() {
    int N = 100;
    int a = 2, b = 3, c = 5;
    cout << "1到100中能被2,3,5之一整除的数有: " 
         << count_divisible(N, a, b, c) << "个" << endl;
    return 0;
}

输出：74（你手动验证一下：2的倍数50个，3的倍数33个，5的倍数20个，两两交集：6的倍数16个，10的倍数10个，15的倍数6个，三个交集30的倍数3个，则50+33+20-16-10-6+3=74）

Python 代码（简化版）

def count_divisible(N, a, b, c):
    """直接公式计算，假设备数互质"""
    cnt_a = N // a
    cnt_b = N // b
    cnt_c = N // c
    cnt_ab = N // (a * b)  # 实际应为lcm
    cnt_ac = N // (a * c)
    cnt_bc = N // (b * c)
    cnt_abc = N // (a * b * c)
    return cnt_a + cnt_b + cnt_c - cnt_ab - cnt_ac - cnt_bc + cnt_abc

N = 100
a, b, c = 2, 3, 5
print(f"1到{N}中能被{a},{b},{c}之一整除的数有: {count_divisible(N, a, b, c)}个")

4.2 通用容斥：任意个除数（使用最小公倍数）

当除数的个数不固定，或者除数之间不互质时，我们需要用 最小公倍数 (lcm) 来计算交集的大小。求 lcm 的公式：lcm(a, b) = a / gcd(a, b) * b。下面的代码实现了通用版本，枚举所有非空子集，每次计算子集内所有除数的 lcm，并根据子集大小（奇偶）决定加减。

C++ 通用版本（带 lcm）

#include <iostream>
#include <vector>
#include <algorithm> // for __gcd in C++17, or use std::gcd in <numeric>
using namespace std;

// 求最小公倍数（注意防溢出）
long long lcm(long long a, long long b) {
    return a / __gcd(a, b) * b;  // 先除后乘可避免溢出
}

// 通用容斥：求1..N中能被任意一个除数整除的数的个数
int inclusion_exclusion(int N, vector<int>& divisors) {
    int n = divisors.size();
    int total = 0;
    // 枚举所有非空子集，mask从1到(1<<n)-1
    for (int mask = 1; mask < (1 << n); mask++) {
        int bits = 0;           // 当前子集中的元素个数
        long long current_lcm = 1;  // 当前子集所有除数的最小公倍数
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                bits++;
                current_lcm = lcm(current_lcm, divisors[i]);
                if (current_lcm > N) break;  // lcm超过N就没意义了，提前退出
            }
        }
        if (current_lcm <= N) {  // 只有当lcm<=N时才有贡献
            if (bits % 2 == 1) {
                total += N / current_lcm;   // 奇数个集合：加
            } else {
                total -= N / current_lcm;   // 偶数个集合：减
            }
        }
    }
    return total;
}

int main() {
    int N = 100;
    vector<int> divisors = {2, 3, 5};
    cout << "1到" << N << "中能被2,3,5之一整除的数有: " 
         << inclusion_exclusion(N, divisors) << "个" << endl;

    // 另一个例子：求100以内能被4或6整除的数（4和6不互质，乘积=24，lcm=12）
    vector<int> divisors2 = {4, 6};
    cout << "1到" << N << "中能被4或6整除的数有: " 
         << inclusion_exclusion(N, divisors2) << "个" << endl;
    // 验证：4的倍数25个，6的倍数16个，12的倍数8个 => 25+16-8=33
    return 0;
}

Python 通用版本（带 lcm）

import math

def inclusion_exclusion(N, divisors):
    """通用容斥，使用最小公倍数"""
    n = len(divisors)
    total = 0
    for mask in range(1, 1 << n):
        bits = 0
        lcm_val = 1
        for i in range(n):
            if mask & (1 << i):
                bits += 1
                lcm_val = lcm_val // math.gcd(lcm_val, divisors[i]) * divisors[i]
                if lcm_val > N:
                    break
        else:  # 循环没有break（即lcm_val未超过N）
            if bits % 2 == 1:
                total += N // lcm_val
            else:
                total -= N // lcm_val
    return total

# 测试
N = 100
print("1到100中能被2,3,5之一整除的数有:", inclusion_exclusion(N, [2, 3, 5]))
print("1到100中能被4或6整除的数有:", inclusion_exclusion(N, [4, 6]))

输出：

1到100中能被2,3,5之一整除的数有: 74
1到100中能被4或6整除的数有: 33

5. 编程中常犯的错误

忘记减去两两交集：很多人只把单个集合加起来，就以为完事了，结果多算了重叠部分。
两个数的最小公倍数直接用乘积：当两个数不互质时，比如 4 和 6，乘积是 24，但 lcm 是 12。如果直接用 24 计算交集，就会少算很多数（例如 12 整除的数只被算了一次，实际上应该被算作交集）。正确做法是用 lcm。
没有考虑 lcm 超过 N 的情况：如果子集的 lcm 大于 N，那么 N/lcm = 0，可以提前跳出循环，避免溢出。
枚举子集时忘记排除空集：空集对应的 mask = 0，我们通常从 1 开始循环，避免加 0。
符号弄反：记住“加奇减偶”——奇数个集合的项是加，偶数个集合的项是减（第一个加号对应单个集合，即奇数个）。

6. 完整示例：求不能被任何给定数整除的个数

问题：求 1 到 200 中，不能被 2、3、5 中任何一个整除的数的个数。

思路：先求能被至少一个整除的个数，然后用总数 200 减去它。

import math

def count_not_divisible(N, divisors):
    """求1..N中不能被任何一个除数整除的数的个数"""
    # 先求能被至少一个整除的个数
    total_divisible = inclusion_exclusion(N, divisors)
    # 总数减去即可
    return N - total_divisible

# 测试
N = 200
divisors = [2, 3, 5]
result = count_not_divisible(N, divisors)
print(f"1到{N}中不能被{divisors}中任何一个整除的数有: {result}个")

输出：应该是 200 - (100+66+40 - 33-20-13 + 6) = 200 - 146 = 54 个。

7. 经典应用：错排问题（全错位排列）

容斥原理的另一个经典应用是 错排问题：n 个不同的物品，每个物品不能放在它原来的位置，求有多少种排列（也叫全错位排列）。

例如，有 4 本不同的书，分别属于 4 个同学。现在要重新分配，每人一本，但每人不能拿到自己原来那本书（假设每人喜欢的正好是自己的书）。有多少种分法？

公式：

D(n) = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}

这个公式其实是用容斥原理推导出来的：设 $A_i$ 表示第 i 个物品放在原来位置的排列，则要求 $|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}|$ ，即所有事件都不发生。利用容斥原理，先求所有满足“至少一个在原位”的排列数，再用所有排列数减去。

对于 n=4，D(4)=9。你可以手动验证：4本书全排列有24种，其中至少一本在原位的用容斥可算出15种，所以错排为9。

（更详细的推导这里不展开，感兴趣的同学可以搜索“错排问题”）

8. 相关指引

容斥原理是组合数学中一个非常重要的工具，与以下知识点紧密相连：

最小公倍数 (LCM) 和最大公约数 (GCD)：在计算交集大小时经常用到。
二进制枚举：在编程中，枚举所有子集是容斥的常用实现方法。
概率论：容斥原理也用于计算多个事件至少发生一个的概率。
韦恩图：画图可以帮助理解叠加与扣减的过程。
组合数：容斥公式中的系数与组合数有关，可进一步研究。

掌握容斥原理，你就能轻松解决很多看似复杂的计数问题，比如“1000以内有多少个数是 2、3、5、7 中至少一个的倍数？”或者“把 10 个不同糖果分给 3 个小朋友，每个小朋友至少拿到一颗，有多少种分法？”（这实际上是整数分拆+容斥）。赶快动手试试吧！

练习答案

1到200中不能被2,3,5中任何一个整除的个数：总数200 - 能被至少一个整除的个数146 = 54。
4本书的错排方案数：9。

例题精讲