容斥原理初步

容斥原理是一种在计数时，先把所有包含的部分都加起来，再“排斥”掉重复计算的部分，最后得到不重不漏的正确结果的方法。

- 第一步：把要计数的不同类别分别加起来。 - 第二步：减去所有两两重叠（同时属于两个类别）的部分。 - 第三步：如果涉及三个类别，还要加上三个都重叠的部分（因为减多了）。 - 口诀：“加多加、减多减，最后不漏也不重”。

- 两个集合的容斥公式：|A ∪ B| = |A| + |B| - |A ∩ B| - 三个集合的容斥公式：|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C| （记住：先加所有单个，再减两两重叠，最后加回三重重叠）

- 容易忘记减去重叠部分，导致结果偏大。 - 在三个集合时，容易忘记最后加上三个都重叠的部分（因为之前被多减了一次）。 - 分不清“至少满足一个”和“恰好满足一个”的区别。

竞赛难度的容斥原理，常常结合“整数整除”、“数字条件”或“图形覆盖”来出题，数字设计巧妙，需要先准确找出每一个集合的大小，再准确找出两两、三三的交集大小。重点考察学生逻辑的严密性和分步计算的准确性，往往需要逆向思考。

在1到100这100个自然数中，既不是2的倍数也不是3的倍数也不是5的倍数的数有多少个？

先找出所有是2、3、5倍数的数（分别看作三个集合），然后利用容斥原理求出至少是其中一个倍数的数的个数，最后用总数减去这个数，就得到既不是2、3、5倍数（即一个都不满足）的数的个数。

1. 设A = {1～100中2的倍数}，B = {3的倍数}，C = {5的倍数} 2. 求|A|：100 ÷ 2 = 50（个） 3. 求|B|：100 ÷ 3 = 33余1，所以有33个（3×33=99） 4. 求|C|：100 ÷ 5 = 20（个） 5. 求|A∩B|（即6的倍数）：100 ÷ 6 = 16余4，所以有16个 6. 求|B∩C|（即15的倍数）：100 ÷ 15 = 6余10，所以有6个 7. 求|A∩C|（即10的倍数）：100 ÷ 10 = 10（个） 8. 求|A∩B∩C|（即30的倍数）：100 ÷ 30 = 3余10，所以有3个 9. 根据三个集合容斥原理，至少是2、3、5其中一个倍数的数有： |A∪B∪C| = 50 + 33 + 20 - 16 - 6 - 10 + 3 = 74（个） 10. 既不是2的倍数也不是3的倍数也不是5的倍数的数有： 100 - 74 = 26（个）

26个

遇到“既不是…也不是…也不是…”这种包含“否定”的计数问题时，通常先把“肯定”的部分（即至少满足一个条件的）通过容斥原理算出来，再用总数去减。关键是要准确求出每一个集合以及它们的交集的元素个数。