做網(wǎng)站小編怎么樣做網(wǎng)絡(luò)推廣可以通過(guò)哪些渠道推廣
數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記----容斥原理
@@ author: 明月清了個(gè)風(fēng)
@@ first publish time: 2025.1.30ps??介紹了容斥原理的相關(guān)內(nèi)容以及一道對(duì)應(yīng)的應(yīng)用例題。
Acwing 890. 能被整除的數(shù)
[原題鏈接](890. 能被整除的數(shù) - AcWing題庫(kù))
給定一個(gè)整數(shù) n n n和 m m m個(gè)不同的質(zhì)數(shù) p 1 , p 2 , ? , p m p_1,p_2,\cdots,p_m p1?,p2?,?,pm?。
請(qǐng)你求出 1 ~ n 1 \sim n 1~n中能被 p 1 , p 2 , ? , p m p_1,p_2,\cdots,p_m p1?,p2?,?,pm?中的至少一個(gè)數(shù)整除的整數(shù)有多少個(gè)。
輸入格式
第一行包含整數(shù) n n n和 m m m。
第二行包含 m m m個(gè)質(zhì)數(shù)。
輸出格式
輸出一個(gè)整數(shù),表示滿(mǎn)足條件的整數(shù)的個(gè)數(shù)。
數(shù)據(jù)范圍
1 ≤ m ≤ 16 1 \le m \le 16 1≤m≤16,
1 ≤ n , p i ≤ 1 0 9 1 \le n, p_i \le 10^9 1≤n,pi?≤109
思路
容斥原理是一種重要的組合數(shù)學(xué)方法,用于解決多個(gè)集合的元素計(jì)數(shù)問(wèn)題。它的核心思想是通過(guò)對(duì)集合進(jìn)行交集與并集的操作,減去重復(fù)計(jì)算的部分,從而準(zhǔn)確地計(jì)算出多個(gè)集合的并集中元素的總數(shù)。
- 兩個(gè)集合的容斥原理:
設(shè) A A A和 B B B是兩個(gè)集合,則它們的并集 A ∪ B A \cup B A∪B的元素個(gè)數(shù)為:
∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ ? ∣ A ∩ B ∣ |A \cup B| = |A| + |B| - |A \cap B| ∣A∪B∣=∣A∣+∣B∣?∣A∩B∣
其中, ∣ A ∣ |A| ∣A∣和 ∣ B ∣ |B| ∣B∣分別是集合 A A A和 B B B的元素個(gè)數(shù), ∣ A ∩ B ∣ |A \cap B| ∣A∩B∣是集合 A A A和 B B B的交集的元素個(gè)數(shù)。
- 三個(gè)集合的容斥原理:
設(shè) A A A、 B B B和 C C C是三個(gè)集合,則它們的并集 A ∪ B ∪ C A \cup B \cup C A∪B∪C的元素個(gè)數(shù)為:
∣ A ∪ B ∪ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ ? ∣ A ∩ B ∣ ? ∣ B ∩ C ∣ ? ∣ C ∩ A ∣ + ∣ A ∩ B ∩ C ∣ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C| ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣?∣A∩B∣?∣B∩C∣?∣C∩A∣+∣A∩B∩C∣
其中, ∣ A ∣ |A| ∣A∣、 ∣ B ∣ |B| ∣B∣和 ∣ C ∣ |C| ∣C∣分別是集合 A A A、 B B B和 C C C的元素個(gè)數(shù), ∣ A ∩ B ∣ |A \cap B| ∣A∩B∣、 ∣ B ∩ C ∣ |B \cap C| ∣B∩C∣和 ∣ C ∩ A ∣ |C \cap A| ∣C∩A∣分別是集合 A A A和 B B B、 B B B和 C C C、 C C C和 A A A的交集的元素個(gè)數(shù), ∣ A ∩ B ∩ C ∣ |A \cap B \cap C| ∣A∩B∩C∣是集合 A A A、 B B B和 C C C的交集的元素個(gè)數(shù)。
- n n n個(gè)集合的容斥原理:
設(shè) A 1 , A 2 , … , A n A_1, A_2, \ldots, A_n A1?,A2?,…,An?是 n n n個(gè)集合,則它們的并集 A 1 ∪ A 2 ∪ … ∪ A n A_1 \cup A_2 \cup \ldots \cup A_n A1?∪A2?∪…∪An?的元素個(gè)數(shù)為:
∣ A 1 ∪ A 2 ∪ … ∪ A n ∣ = ∑ i = 1 n ∣ A i ∣ ? ∑ 1 ≤ i < j ≤ n ∣ A i ∩ A j ∣ + ∑ 1 ≤ i < j < k ≤ n ∣ A i ∩ A j ∩ A k ∣ ? ? + ( ? 1 ) n ? 1 ∣ A 1 ∩ A 2 ∩ … ∩ A n ∣ |A_1 \cup A_2 \cup \ldots \cup A_n| = \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} |A_1 \cap A_2 \cap \ldots \cap A_n| ∣A1?∪A2?∪…∪An?∣=∑i=1n?∣Ai?∣?∑1≤i<j≤n?∣Ai?∩Aj?∣+∑1≤i<j<k≤n?∣Ai?∩Aj?∩Ak?∣??+(?1)n?1∣A1?∩A2?∩…∩An?∣
其中,求和符號(hào)表示對(duì)所有可能的集合組合進(jìn)行求和, ( ? 1 ) n ? 1 (-1)^{n-1} (?1)n?1表示當(dāng)集合的交集數(shù)量(即下標(biāo)集合的大小)為奇數(shù)時(shí)取正號(hào),為偶數(shù)時(shí)取負(fù)號(hào)。
對(duì)于 n n n個(gè)集合的容斥原理公式來(lái)說(shuō),最后共有 2 n 2^n 2n項(xiàng),因?yàn)槊恳豁?xiàng)都可以看做是一個(gè)組合數(shù),比如 ∑ i = 1 n ∣ A i ∣ \sum_{i=1}^{n}|A_i| ∑i=1n?∣Ai?∣中共有是 n n n項(xiàng),因?yàn)橄喈?dāng)于 C n 1 C_{n}^{1} Cn1?種方案數(shù);對(duì)于 ∑ 1 ≤ i < j ≤ n ∣ A i ∩ A j ∣ \sum_{1 \leq i < j \leq n} |A_i \cap A_j| ∑1≤i<j≤n?∣Ai?∩Aj?∣也同樣是這樣,相當(dāng)于 C n 2 C_{n}^{2} Cn2?種方案數(shù);那么所有的項(xiàng)目就相當(dāng)于 C n 1 + C n 2 + C n 3 + ? + C n n = 2 n ? 1 C_n^{1} + C_n^{2} + C_n^{3} + \cdots + C_n^{n} = 2^n - 1 Cn1?+Cn2?+Cn3?+?+Cnn?=2n?1項(xiàng),但是其實(shí)所有集合都不選也是一項(xiàng),也就是 C n 0 C_n^0 Cn0?,只是沒(méi)有顯式的計(jì)算他,因此最開(kāi)始說(shuō)共有 2 n 2^n 2n項(xiàng)。
y總還講了另外一個(gè)等式,這個(gè)式子表明了容斥原理的核心思想:每個(gè)元素只被統(tǒng)計(jì)一次。
C k 1 ? C k 2 + C k 3 ? … + ( ? 1 ) k + 1 C k k = 1 C_{k}^{1} - C_{k}^{2} + C_{k}^{3} - \ldots + (-1)^{k+1}C_{k}^{k} = 1 Ck1??Ck2?+Ck3??…+(?1)k+1Ckk?=1
這個(gè)等式表明,在容斥原理的交替求和公式中,每個(gè)元素在所有可能的集合組合(交集)中出現(xiàn)的次數(shù),經(jīng)過(guò)正負(fù)交替相加后,總和等于1,從而確保了每個(gè)元素在最終的計(jì)算中只被統(tǒng)計(jì)了一次。
這里再回到題目來(lái)看,我們需要統(tǒng)計(jì) 1 ~ n 1 \sim n 1~n中至少被一個(gè)所給的數(shù)整除的數(shù)有多少個(gè),也就是說(shuō)如果一個(gè)數(shù)能被好幾個(gè)數(shù)整除,也只統(tǒng)計(jì)一次,如果我們用暴力做法,需要對(duì) n n n個(gè)數(shù)都遍歷 m m m個(gè)數(shù)對(duì)比,時(shí)間復(fù)雜度為 O ( n ? m ) O(n \cdot m) O(n?m)會(huì)超時(shí),但是我們使用容斥原理進(jìn)行統(tǒng)計(jì)的話,就能將時(shí)間復(fù)雜度降低到 O ( 2 m ) O(2^m) O(2m)。
首先,對(duì)于每一個(gè)給出的質(zhì)數(shù)p_i,都會(huì)有一個(gè)集合表示所有能被他整除的數(shù),要關(guān)注的是這個(gè)集合中元素的個(gè)數(shù),而不是這些數(shù)是哪些數(shù)。這個(gè)數(shù)量我們可以通過(guò) ? n p i ? \lfloor \frac{n}{p_i} \rfloor ?pi?n??計(jì)算得出,同樣的對(duì)于同時(shí)是多個(gè)質(zhì)數(shù)的倍數(shù)的集合中元素的個(gè)數(shù)也可以這樣計(jì)算得到,例如 ? n p i p j ? \lfloor \frac{n}{p_i p_j} \rfloor ?pi?pj?n??的形式,我們可以通過(guò)這樣的方式處理出所有集合包含元素的個(gè)數(shù)。
然后,通過(guò)對(duì)上面n個(gè)元素對(duì)應(yīng)的容斥原理計(jì)算公式進(jìn)行觀察可以發(fā)現(xiàn),當(dāng)一個(gè)元素被包含在偶數(shù)個(gè)集合中時(shí),那就應(yīng)該減去,集合數(shù)為奇數(shù)時(shí)加上,同樣用上面的來(lái)舉例,所有的只被一個(gè)質(zhì)數(shù)整除的元素集合的數(shù)目 ? n p i ? \lfloor \frac{n}{p_i} \rfloor ?pi?n??都應(yīng)該被加到答案 r e s res res中區(qū),所有被兩個(gè)質(zhì)數(shù)整除的元素集合的數(shù)目 ? n p i p j ? \lfloor \frac{n}{p_i p_j} \rfloor ?pi?pj?n??都應(yīng)該從答案中減去。
至此,題目的思路已經(jīng)理清了,需要考慮的是代碼的邏輯,我們要統(tǒng)計(jì)的有兩個(gè)東西
- 所有集合的大小。
- 每個(gè)集合是能被幾個(gè)質(zhì)數(shù)整除。
這里就用到了上面對(duì)于容斥原理公式包含項(xiàng)數(shù)的結(jié)果了,一共 2 m ? 1 2^m - 1 2m?1項(xiàng),一共有 m m m個(gè)質(zhì)數(shù),那么我們可以通過(guò)統(tǒng)計(jì) 1 ~ 2 m 1 \sim 2^m 1~2m,一共 2 m ? 1 2^m - 1 2m?1個(gè)數(shù)代表所有的集合,每個(gè)數(shù)的二進(jìn)制表示中的 1 1 1的數(shù)量表示這個(gè)集合是被幾個(gè)質(zhì)數(shù)整除的,同時(shí),集合的大小可以在這個(gè)過(guò)程中同時(shí)處理出來(lái),將所有質(zhì)數(shù)存在數(shù)組p[N]
中,記錄一個(gè)數(shù)t = 1
,當(dāng)?shù)?code>i位為1
時(shí),就將t *= p[i]
,遍歷完這個(gè)數(shù)的二進(jìn)制的所有位后,通過(guò)num = n / t
得到該集合的大小,具體的看代碼吧
代碼
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;typedef long long LL;const int N = 20;int p[N];
int n, m;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 ++){int t = 1, cnt = 0;for(int j = 0; j < m; j ++){if(i >> j & 1){if((LL)t * p[j] > n){t = -1;break;}t *= p[j];cnt ++;}}if(t == -1) continue;if(cnt % 2) res += n / t;else res -= n / t;}cout << res << endl;return 0;
}