數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記----容斥原理

@@ author: 明月清了個(gè)風(fēng)
@@ first publish time: 2025.1.30

ps??介紹了容斥原理的相關(guān)內(nèi)容以及一道對(duì)應(yīng)的應(yīng)用例題。

---

Acwing 890. 能被整除的數(shù)

[原題鏈接](890. 能被整除的數(shù) - AcWing題庫(kù))

給定一個(gè)整數(shù)$n$和$m$個(gè)不同的質(zhì)數(shù)$p_1,p_2,?,p_m$。

請(qǐng)你求出$1～n$中能被$p_1,p_2,?,p_m$中的至少一個(gè)數(shù)整除的整數(shù)有多少個(gè)。

輸入格式

第一行包含整數(shù)$n$和$m$。

第二行包含$m$個(gè)質(zhì)數(shù)。

輸出格式

輸出一個(gè)整數(shù)，表示滿(mǎn)足條件的整數(shù)的個(gè)數(shù)。

數(shù)據(jù)范圍

$1\le m\le 16$,

$1\le n,p_i\le 10^9$

思路

容斥原理是一種重要的組合數(shù)學(xué)方法，用于解決多個(gè)集合的元素計(jì)數(shù)問(wèn)題。它的核心思想是通過(guò)對(duì)集合進(jìn)行交集與并集的操作，減去重復(fù)計(jì)算的部分，從而準(zhǔn)確地計(jì)算出多個(gè)集合的并集中元素的總數(shù)。

1. 兩個(gè)集合的容斥原理：

設(shè)$A$和$B$是兩個(gè)集合，則它們的并集$A\cup B$的元素個(gè)數(shù)為：

$|A\cup B|=|A|+|B|?|A\cap B|$

其中，$|A|$和$|B|$分別是集合$A$和$B$的元素個(gè)數(shù)，$|A\cap B|$是集合$A$和$B$的交集的元素個(gè)數(shù)。

2. 三個(gè)集合的容斥原理：

設(shè)$A$、$B$和$C$是三個(gè)集合，則它們的并集$A\cup B\cup C$的元素個(gè)數(shù)為：

$|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$的元素個(gè)數(shù)，$|A\cap B|$、$|B\cap C|$和$|C\cap A|$分別是集合$A$和$B$、$B$和$C$、$C$和$A$的交集的元素個(gè)數(shù)，$|A\cap B\cap C|$是集合$A$、$B$和$C$的交集的元素個(gè)數(shù)。

3. $n$個(gè)集合的容斥原理：

設(shè)$A_1,A_2,\dots ,A_n$是$n$個(gè)集合，則它們的并集$A_1\cup A_2\cup \dots \cup A_n$的元素個(gè)數(shù)為：

$|A_1\cup A_2\cup \dots \cup A_n|={\sum }_{i=1}^n|A_i|?{\sum }_{1\le i<j\le n}|A_i\cap A_j|+{\sum }_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|??+(?1{)}^{n?1}|A_1\cap A_2\cap \dots \cap A_n|$

其中，求和符號(hào)表示對(duì)所有可能的集合組合進(jìn)行求和，$(?1{)}^{n?1}$表示當(dāng)集合的交集數(shù)量（即下標(biāo)集合的大小）為奇數(shù)時(shí)取正號(hào)，為偶數(shù)時(shí)取負(fù)號(hào)。

對(duì)于$n$個(gè)集合的容斥原理公式來(lái)說(shuō)，最后共有$2^n$項(xiàng)，因?yàn)槊恳豁?xiàng)都可以看做是一個(gè)組合數(shù)，比如${\sum }_{i=1}^n|A_i|$中共有是$n$項(xiàng)，因?yàn)橄喈?dāng)于$C_n^1$種方案數(shù)；對(duì)于${\sum }_{1\le i<j\le n}|A_i\cap A_j|$也同樣是這樣，相當(dāng)于$C_n^2$種方案數(shù)；那么所有的項(xiàng)目就相當(dāng)于$C_n^1+C_n^2+C_n^3+?+C_n^n=2^n?1$項(xiàng)，但是其實(shí)所有集合都不選也是一項(xiàng)，也就是$C_n^0$，只是沒(méi)有顯式的計(jì)算他，因此最開(kāi)始說(shuō)共有$2^n$項(xiàng)。

y總還講了另外一個(gè)等式，這個(gè)式子表明了容斥原理的核心思想：每個(gè)元素只被統(tǒng)計(jì)一次。
$$C_k^1?C_k^2+C_k^3?\dots +(?1{)}^{k+1}{C}_k^k=1$$
這個(gè)等式表明，在容斥原理的交替求和公式中，每個(gè)元素在所有可能的集合組合（交集）中出現(xiàn)的次數(shù)，經(jīng)過(guò)正負(fù)交替相加后，總和等于1，從而確保了每個(gè)元素在最終的計(jì)算中只被統(tǒng)計(jì)了一次。

這里再回到題目來(lái)看，我們需要統(tǒng)計(jì)$1～n$中至少被一個(gè)所給的數(shù)整除的數(shù)有多少個(gè)，也就是說(shuō)如果一個(gè)數(shù)能被好幾個(gè)數(shù)整除，也只統(tǒng)計(jì)一次，如果我們用暴力做法，需要對(duì)$n$個(gè)數(shù)都遍歷$m$個(gè)數(shù)對(duì)比，時(shí)間復(fù)雜度為$O(n?m)$會(huì)超時(shí)，但是我們使用容斥原理進(jìn)行統(tǒng)計(jì)的話，就能將時(shí)間復(fù)雜度降低到$O(2^m)$。

首先，對(duì)于每一個(gè)給出的質(zhì)數(shù)p_i，都會(huì)有一個(gè)集合表示所有能被他整除的數(shù)，要關(guān)注的是這個(gè)集合中元素的個(gè)數(shù)，而不是這些數(shù)是哪些數(shù)。這個(gè)數(shù)量我們可以通過(guò)$?\frac{n}{p_i}?$計(jì)算得出，同樣的對(duì)于同時(shí)是多個(gè)質(zhì)數(shù)的倍數(shù)的集合中元素的個(gè)數(shù)也可以這樣計(jì)算得到，例如$?\frac{n}{p_i{p}_j}?$的形式，我們可以通過(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ù)目$?\frac{n}{p_i}?$都應(yīng)該被加到答案$res$中區(qū)，所有被兩個(gè)質(zhì)數(shù)整除的元素集合的數(shù)目$?\frac{n}{p_i{p}_j}?$都應(yīng)該從答案中減去。

至此，題目的思路已經(jīng)理清了，需要考慮的是代碼的邏輯，我們要統(tǒng)計(jì)的有兩個(gè)東西

1. 所有集合的大小。
2. 每個(gè)集合是能被幾個(gè)質(zhì)數(shù)整除。

這里就用到了上面對(duì)于容斥原理公式包含項(xiàng)數(shù)的結(jié)果了，一共$2^m?1$項(xiàng)，一共有$m$個(gè)質(zhì)數(shù)，那么我們可以通過(guò)統(tǒng)計(jì)$1～2^m$，一共$2^m?1$個(gè)數(shù)代表所有的集合，每個(gè)數(shù)的二進(jìn)制表示中的$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;
}