文章目錄
-
- 原理
- 證明
- 例題
原理
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|) ，這就是容斥原理的公式
很容易發現，如果某一項包含奇數個集合時，那麼它的符号就是"＋"，反之，某一項包含偶數個集合時，它的符号就是"-"。
證明
為什麼容斥原理是對的呢？
不妨設一個元素 x(x ∈ S1 ∪ S2 ∪ … ∪ S n) 出現在了 k (1≤ k ≤n)個集合中，那麼 x 一共會被算C ( 1 k ) \tbinom{1}{k} (k1) - C ( 2 k ) \tbinom{2}{k} (k2) + C ( 3 k ) \tbinom{3}{k} (k3) - C ( 4 k ) \tbinom{4}{k} (k4) + … + (-1)k-1C ( k k ) \tbinom{k}{k} (kk)，這個式子是恒等于 1 的(可以證明)。是以，任意 1 個元素 x 隻被加了一次，是以說容斥原理是正确的。
上面已經知道計算 3 個集合的并集的元素個數的式子有 7 項，計算4 個集合并集的元素個數的式子有 15 項。
大膽猜測一下，計算 n 個集合的并集的元素個數的式子一共有 2n - 1 項。
證明：
C ( 0 n ) \tbinom{0}{n} (n0) + 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
①等式右邊代表從 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，得證
例題
樣例：
1、2、3、4、5、6、7、8、9、10，質數p={2、3}
2 的倍數的有S2 = {2、4、6、8、10} 5個
3 的倍數的有S3 = {3、6、9} 3個
既是 2 的倍數，也是 3 的倍數的有 S2 ∩ S3 = {6} 1個
是以，5 + 3 - 1 = 7 個
那麼，1~n 中 p 的倍數的個數怎麼求呢？
答： n/p
既是 pi 的倍數，也是 pj 和 pk 的倍數的個數是 n/pipjpk
思路：
二進制，已知共有 2m - 1 項，每一項所包含的質數都不同，我們可以用 1~2m-1 這 2m - 1 個數，來表示不同的項，每個數都轉換成 m 位二進制數後，這 m 位就分别代表着 m 個質數是否包含，1代表包含，0代表不包含
AcWing 890. 能被整除的數
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 20;
int n,m;
int p[N];
int main()
{
cin >> n >> m;
for(int i = 0; i < m; i++) cin >> p[i];
int res = 0;
for(int i = 1; i< 1 << m; i++) // 1~2^m-1這些數代表2^m-1個不同的項
{
int t = 1, cnt = 0; //cnt代表目前枚舉的項中包含集合的個數
for(int j=0; j<m; j++)//看這個項的第 j 位是否包含，1代表包含，0代表不包含
if(i >> j & 1) //選
{
if((LL)t * p[j] > n) //此時 n/t = 0，直接break即可
{
t = -1;
break;
}
cnt++;
t *= p[j];
}
if(t != -1)
{
if(cnt % 2) res += n/t; //加奇數項的個數
else res -= n/t; //減偶數項的個數
}
}
cout << res;
}
時間複雜度：
O(2^m * m)