一、容斥原理

定义

容斥原理（Inclusion-Exclusion Principle）是计算多个集合并集元素个数的核心方法，通过加减交集的方式消除重复计数。其核心公式为：
对任意有限集合 $A_1, A_2, \ldots, A_n$，有：

$$|A_1 \cup A_2 \cup \cdots \cup A_n| = \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 \cdots \cap A_n|$$

二、例题：计算1-10000中不能被4、5、6整除的数的个数

步骤解析

1. 定义集合：

   • $A$：能被4整除的数的集合
   • $B$：能被5整除的数的集合
   • $C$：能被6整除的数的集合

2. 计算单个集合大小：

   • $|A| = \lfloor \frac{10000}{4} \rfloor = 2500$
   • $|B| = \lfloor \frac{10000}{5} \rfloor = 2000$
   • $|C| = \lfloor \frac{10000}{6} \rfloor = 1666$

3. 计算两两交集：

   • $|A \cap B| = \lfloor \frac{10000}{LCM(4,5)} \rfloor = \lfloor \frac{10000}{20} \rfloor = 500$
   • $|A \cap C| = \lfloor \frac{10000}{LCM(4,6)} \rfloor = \lfloor \frac{10000}{12} \rfloor = 833$
   • $|B \cap C| = \lfloor \frac{10000}{LCM(5,6)} \rfloor = \lfloor \frac{10000}{30} \rfloor = 333$

4. 计算三集合交集：

   • $|A \cap B \cap C| = \lfloor \frac{10000}{LCM(4,5,6)} \rfloor = \lfloor \frac{10000}{60} \rfloor = 166$

5. 应用容斥原理：

$$\begin{align*} |A \cup B \cup C| &= 2500 + 2000 + 1666 - 500 - 833 - 333 + 166 \\ &= 2500 + 2000 = 4500 \\ &+ 1666 = 6166 \\ &- 500 = 5666 \\ &- 833 = 4833 \\ &- 333 = 4500 \\ &+ 166 = 4666 \end{align*}$$

6. 求补集：
   • 总数10000中，不能被4、5、6整除的数的个数为：

   $$10000 - 4666 = 5334$$

关键点：

• 最小公倍数 (LCM)：计算交集时需用最小公倍数而非乘积（如LCM(4,5)=20）；
• 向下取整：整除计数需向下取整（如$\lfloor 10000/6 \rfloor = 1666$）。

更新日志

2025/3/16 17:14

查看所有更新日志

• 8739a-update于 2025/3/16

版权所有

版权归属：NateHHX

许可证：署名 4.0 国际 (CC-BY-4.0)