惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

M
MIT News - Artificial intelligence
WordPress大学
WordPress大学
GbyAI
GbyAI
S
SegmentFault 最新的问题
量子位
爱范儿
爱范儿
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
MyScale Blog
MyScale Blog
人人都是产品经理
人人都是产品经理
博客园 - 叶小钗
aimingoo的专栏
aimingoo的专栏
V
Visual Studio Blog
U
Unit 42
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
The Cloudflare Blog
Stack Overflow Blog
Stack Overflow Blog
博客园 - 聂微东
J
Java Code Geeks
The GitHub Blog
The GitHub Blog
Y
Y Combinator Blog
IT之家
IT之家
Martin Fowler
Martin Fowler
宝玉的分享
宝玉的分享
雷峰网
雷峰网

博客园 - ace--碳水化合物

用ClaudeCode改简历 韦达定理 韦达定理1 梯形1 总平均分 m1 曲线相关 曲线 不等式 抛硬币 错位排列"(全错位)问题 11 1 两圆阴影面积 English1 Tidio 官方帮助中心 ERP 相关系统介绍 蝉翼定理 选配法 利润最大化公式 写在失业的一段话 排列组合-组合 在线简历 概率论与数理统计学习章节 绝对值 比例五大定理 算术平均值与几何平均值 等价符号 公因数与最大公因数 英语2026
容斥原理
ace--碳水化合物 · 2026-05-31 · via 博客园 - ace--碳水化合物

容斥原理是计算集合并集大小的基本工具。简单说,就是:

先加上各个集合的大小,再减去两两交集的大小,再加回三三交集的大小……依此类推,避免重复计数。


1. 两个集合的情况

对于两个集合 ( A ) 和 ( B ):
[
|A \cup B| = |A| + |B| - |A \cap B|
]

  • 加两次交集部分会重复,所以要减去一次。

图示理解:

  A       B
 (   ∩   )

交集被数了两次,需减去一次。


2. 三个集合的情况

[
|A \cup B \cup C| = |A| + |B| + |C|

  • |A \cap B| - |A \cap C| - |B \cap C|
  • |A \cap B \cap C|
    ]
  • 先加单个集合,减去两两重叠(重复算了两次),再加回三重重叠(因为被减多了)。

3. 刚才题中的应用

题中:

  • ( A ):能被 5 整除的数,( |A| = 20 )
  • ( B ):能被 7 整除的数,( |B| = 14 )
  • ( A \cap B ):能同时被 5 和 7 整除(即被 35 整除),( |A \cap B| = 2 )

用容斥原理:
[
|A \cup B| = 20 + 14 - 2 = 32
]
这样就把重复计算的两个数(35 和 70)只算了一次。


如果你想看更一般的 ( n ) 个集合的公式或推广,我也可以展开讲。