数据结构与算法学习笔记----容斥原理

数据结构与算法学习笔记----容斥原理

@@ author: 明月清了个风
@@ first publish time: 2025.1.30

ps⭐️介绍了容斥原理的相关内容以及一道对应的应用例题。

---

Acwing 890. 能被整除的数

[原题链接](890. 能被整除的数 - AcWing题库)

给定一个整数$n$和$m$个不同的质数$p_1,p_2,\cdots ,p_m$。

请你求出$1\sim n$中能被$p_1,p_2,\cdots ,p_m$中的至少一个数整除的整数有多少个。

输入格式

第一行包含整数$n$和$m$。

第二行包含$m$个质数。

输出格式

输出一个整数，表示满足条件的整数的个数。

数据范围

$1\le m\le 16$,

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

思路

容斥原理是一种重要的组合数学方法，用于解决多个集合的元素计数问题。它的核心思想是通过对集合进行交集与并集的操作，减去重复计算的部分，从而准确地计算出多个集合的并集中元素的总数。

1. 两个集合的容斥原理：

设$A$和$B$是两个集合，则它们的并集$A\cup B$的元素个数为：

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

其中，$|A|$和$|B|$分别是集合$A$和$B$的元素个数，$|A\cap B|$是集合$A$和$B$的交集的元素个数。

2. 三个集合的容斥原理：

设$A$、$B$和$C$是三个集合，则它们的并集$A\cup B\cup 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\cap B|$、$|B\cap C|$和$|C\cap A|$分别是集合$A$和$B$、$B$和$C$、$C$和$A$的交集的元素个数，$|A\cap B\cap C|$是集合$A$、$B$和$C$的交集的元素个数。

3. $n$个集合的容斥原理：

设$A_1,A_2,\dots ,A_n$是$n$个集合，则它们的并集$A_1\cup A_2\cup \dots \cup A_n$的元素个数为：

$|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|-\cdots +(-1{)}^{n-1}|A_1\cap A_2\cap \dots \cap A_n|$

其中，求和符号表示对所有可能的集合组合进行求和，$(-1{)}^{n-1}$表示当集合的交集数量（即下标集合的大小）为奇数时取正号，为偶数时取负号。

对于$n$个集合的容斥原理公式来说，最后共有$2^n$项，因为每一项都可以看做是一个组合数，比如${\sum }_{i=1}^n|A_i|$中共有是$n$项，因为相当于$C_n^1$种方案数；对于${\sum }_{1\le i<j\le n}|A_i\cap A_j|$也同样是这样，相当于$C_n^2$种方案数；那么所有的项目就相当于$C_n^1+C_n^2+C_n^3+\cdots +C_n^n=2^n-1$项，但是其实所有集合都不选也是一项，也就是$C_n^0$，只是没有显式的计算他，因此最开始说共有$2^n$项。

y总还讲了另外一个等式，这个式子表明了容斥原理的核心思想：每个元素只被统计一次。
$$C_k^1-C_k^2+C_k^3-\dots +(-1{)}^{k+1}{C}_k^k=1$$
这个等式表明，在容斥原理的交替求和公式中，每个元素在所有可能的集合组合（交集）中出现的次数，经过正负交替相加后，总和等于1，从而确保了每个元素在最终的计算中只被统计了一次。

这里再回到题目来看，我们需要统计$1\sim n$中至少被一个所给的数整除的数有多少个，也就是说如果一个数能被好几个数整除，也只统计一次，如果我们用暴力做法，需要对$n$个数都遍历$m$个数对比，时间复杂度为$O(n\cdot m)$会超时，但是我们使用容斥原理进行统计的话，就能将时间复杂度降低到$O(2^m)$。

首先，对于每一个给出的质数p_i，都会有一个集合表示所有能被他整除的数，要关注的是这个集合中元素的个数，而不是这些数是哪些数。这个数量我们可以通过$\lfloor \frac{n}{p_i}\rfloor$计算得出，同样的对于同时是多个质数的倍数的集合中元素的个数也可以这样计算得到，例如$\lfloor \frac{n}{p_i{p}_j}\rfloor$的形式，我们可以通过这样的方式处理出所有集合包含元素的个数。

然后，通过对上面n个元素对应的容斥原理计算公式进行观察可以发现，当一个元素被包含在偶数个集合中时，那就应该减去，集合数为奇数时加上，同样用上面的来举例，所有的只被一个质数整除的元素集合的数目$\lfloor \frac{n}{p_i}\rfloor$都应该被加到答案$res$中区，所有被两个质数整除的元素集合的数目$\lfloor \frac{n}{p_i{p}_j}\rfloor$都应该从答案中减去。

至此，题目的思路已经理清了，需要考虑的是代码的逻辑，我们要统计的有两个东西

1. 所有集合的大小。
2. 每个集合是能被几个质数整除。

这里就用到了上面对于容斥原理公式包含项数的结果了，一共$2^m-1$项，一共有$m$个质数，那么我们可以通过统计$1\sim 2^m$，一共$2^m-1$个数代表所有的集合，每个数的二进制表示中的$1$的数量表示这个集合是被几个质数整除的，同时，集合的大小可以在这个过程中同时处理出来，将所有质数存在数组p[N]中，记录一个数t = 1，当第i位为1时，就将t *= p[i]，遍历完这个数的二进制的所有位后，通过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;
}