原理
S1、S2 、S3 分别代表下图三个圆1、2、3的面积
如果我们想求下面图形构成的面积，该怎么求呢，很简单
S = S1 ∪ S2 ∪ S3=
S1 + S2 + S3
-S1 ∩ S2 – S1 ∩ S3 – S2 ∩ S3
+S1 ∩ S2 ∩ S3
拓展一下，如果是4个圆的面积应该是
S =S1 ∪ S2 ∪ S3 ∪ S 4 =
S1 + S2 + S3 + S4
-S1 ∩ S2 – S1 ∩ S3 – S1 ∩ S4 – S2 ∩ S3 – S2 ∩ S4 – S3 ∩ S4
+S1 ∩ S2 ∩ S3 + S1 ∩ S2 ∩ S4 + S1 ∩ S3 ∩ S4 + S2 ∩ S3 ∩ S4
-S1 ∩ S2 ∩ S3 ∩ S4
可以发现规律 ，S1 ∪ S2 ∪ … ∪ S n = ( ∑ i = 1 n \sum_{i=1}^n ∑i=1nSi) – ( ∑ i ， j = 1 n \sum_{i，j=1}^n ∑i，j=1n Si ∩ Sj) + ( ∑ i ， j ， k = 1 n \sum_{i，j，k=1}^n ∑i，j，k=1n Si ∩ Sj ∩ Sk) -…+ ((-1)n-1 ∑ i ， j ， k . . . . = 1 n \sum_{i，j，k….=1}^n ∑i，j，k....=1n Si ∩ Sj ∩ Sk ∩…∩ Sn)
上面的是用面积来考虑，如果我们用集合来考虑的话， 若 |S| 代表3个集合并集元素的个数，则：
|S| = |S1 ∪ S2 ∪ S3|=
|S1| + |S2| + |S3|
-|S1 ∩ S2| – |S1 ∩ S3| – |S2 ∩ S3|
+|S1 ∩ S2 ∩ S3|
设 n 个集合并集的元素个数为 |S1 ∪ S2 ∪ … ∪ S n|
那么，|S1 ∪ S2 ∪ … ∪ S n| = ( ∑ i = 1 n \sum_{i=1}^n ∑i=1n|Si|) – ( ∑ i ， j = 1 n \sum_{i，j=1}^n ∑i，j=1n| Si ∩ Sj|) + ( ∑ i ， j ， k = 1 n \sum_{i，j，k=1}^n ∑i，j，k=1n |Si ∩ Sj ∩ Sk|) -…+ ((-1)n-1 ∑ i ， j ， k . . . . = 1 n \sum_{i，j，k….=1}^n ∑i，j，k....=1n |Si ∩ Sj ∩ Sk ∩…∩ Sn|) ，这就是容斥原理的公式
很容易发现，如果某一项包含奇数个集合时，那么它的符号就是”＋“，反之，某一项包含偶数个集合时，它的符号就是”–“。
证明
上面已经知道计算 3 个集合的并集的元素个数的式子有 7 项，计算4 个集合并集的元素个数的式子有 15 项。
大胆猜测一下，计算 n 个集合的并集的元素个数的式子一共有 2n – 1 项。
①等式右边代表从 n 个数中选任意多个数的方案数，因为第一个数选或不选有两种方案，第二个数选或不选两种方案，第三个数…第n个数…总共 2n。
②等式左边代表从 n 个数中选 0 个数的方案数 + 从 n 个数中选 1 个数的方案数 + … +从 n 个数中选 n 个数的方案数。
很明显，①②两者的意义是相同的，所以等号成立。
C ( 1 n ) \tbinom{1}{n} (n1) + C ( 2 n ) \tbinom{2}{n} (n2) + C ( 3 n ) \tbinom{3}{n} (n3) + … + C ( n n ) \tbinom{n}{n} (nn) = 2n – 1，得证
例题
样例：
所以，5 + 3 – 1 = 7 个
思路：二进制，已知共有 2m – 1 项，每一项所包含的质数都不同，我们可以用 1~2m-1 这 2m – 1 个数，来表示不同的项，每个数都转换成 m 位二进制数后，这 m 位就分别代表着 m 个质数是否包含，1代表包含，0代表不包含
AcWing 890. 能被整除的数
#include
时间复杂度：O(2^m * m)
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/224234.html原文链接：https://javaforall.net
