一、容斥原理理论知识
韦恩图（又称文氏图）
（1）两个圆相交的那部分面积。
（2）三个圆相交的那部分面积。
\(S=S_1+S_2+S_3- S_1\cap S_2 -S_2\cap S_3 - S_1\cap S_3 + S_1\cap S_2 \cap S_3\)
遇事不决，小学数学。
（3）四个圆相交的那部分面积。
$S=S_1+S_2 + S_3 + S_3 \(
\)\ \ \ -S_1\cap S_2 -S_1\cap S_3 -S_1\cap S_4 - S_2\cap S_3 -S_2\cap S_4 -S_3\cap S_4\(
\)\ \ + S_1\cap S_2 \cap S_3 + S_1\cap S_2 \cap S_4+ S_2\cap S_3 \cap S_4 ++ S_1\cap S_3 \cap S_4\(
\)\ \ - S_1 \cap S_2 \cap S_3 \cap S_4$
上面，我们是用面积来考虑的问题，所以等式左边写的是S，也可以用集合来考虑，那就是
\(|S_1 \cup S_2 \cup S_3| =|S_1|+|S_2|+|S_3|- |S_1\cap S_2| -|S_2\cap S_3| - |S_1\cap S_3| + |S_1\cap S_2 \cap S_3|\)
其中\(|\)代表集合中的元素个数。
上面项目的个数有什么规律吗？
上面的求解过程，其实是在求 \(C_n^1 - C_n^2+ ... + {(-1)}^{n-1}C_n^n\)，
也就理解为从n个选择1个，减去从n中选择2个，加上从n中选择3个，减去从n中减去4个...,也可以记为奇数个元素的集合是加，偶数个的（指相交）的集合是减。
根据数学组合数定理，有如下的事实定理：$ C_n^0 +C_n^1 + C_n^2+ ... +C_nn=2n $
证明：
等式右边=从n个数中选任意个数的方案数。
等式左边=从n个数中选择0个数的方案数量+从n个数中选择1个数的方案数量+...
它们俩个的实际意义是一样的，所以是成立的！
根据上面的证明，运算的式子就是没有 \(C_n^0\) 这一项，
也就是在求：$C_n^1 + C_n^2+ ... +C_nn=2n -C_n^0 =2^n-1 $
所以，一定会有\(2^n-1\)项，所以时间复杂度是\(2^n\),注意：这里这所以每个组合数之间都用加法，是因为我们想知道到底我们需要计算多少次，是次数的和，所以一起在用加法，真正的容斥原理的计算是加减加减的，一定要区分开！
经典例题1
容斥原理有个经典题目：一个班每个人都有自己喜欢的科目，有20人喜欢数学，10人喜欢语文，11人喜欢英语，其中3人同时喜欢数学语文，3人同时喜欢语文英语，4人同时喜欢数学英语，2人都喜欢，问全班有多少人？
这个肯定不可以20+10+11的简单计算，因为有人喜欢多个科目，会重复计算，在之前基础上-3-3-4，这时候会发现全部都喜欢的被多减了，再+2。得到班级人数=20+10+11-3-3-4+2
经典例题2
问题：我们在1-10中，找出能被质数2和3整除的数的个数是几个？
方法1:双重循环，挨个去算模是不是等于零，是的话，就count++.
如此办法，时间复杂度为： \(O(n \times m)\) ,其中n是指数字的个数，本题为10，m是指待检查的质数个数，本题个数是2.
可是，如果题目要求n特别大，比如1e9，那么n*m我们是不会在1秒内解决问题的，就是，算法复杂，需要优化。
方法2：容斥原理
\(S_2= \\{2,4,6,8,10 \\} \ S_3=\\{3,6,9\\}\)
原题其实是在求解：
$|S_2 \cup S_3|=|S_2|+|S_3| -|S_2 \cap S_3| $= 5+3-1=7
容斥原理来算的话，时间复杂度是 \(2^n\),本题n其实就是质数的个数，也就是走的m的数据范围，是1<=m<=16,就是\(2^{16}=65536\),那么时间确实是降低了。
二、容斥原理的数学表达式
\[\small \sum_{1<=i<=n}|A_i| - \sum_{1<=i<j<=n}|A_i \cap A_j| + \sum_{1<=i<j<k<=n}|A_i \cap A_j \cap A_k| - ...+{(-1)}^{n-1}|A_1 \cap A_2 \cap ... \cap A_n| \]比如三个质数是2，3，5，那么：\(S_2\)就代表2的倍数集合，\(S_3\)就代表3的倍数集合，\(S_5\)就代表5的倍数集合，
$ \small |S_2 \cup S_3 \cup S_5| = |S_2| + |S_3| +|S_5| -|S_2 \cap S_3| -|S_3 \cap S_5| -|S_2 \cap S_5|+|S_2 \cap S_3 \cap S_5|$
(1)如何计算\(|S_2|\)这样的表达式数值呢？
\(|S_p|\)就是计算1-n中p的倍数集合中的元素个数。它就是等于\(\lfloor \frac{n}{p} \rfloor\),也就是想知道在n中有多少个p,比如，1p,2p,3p,...,kp个。这样上面式子中的单独项目我们就会算了，就是算一个\(\lfloor \frac{n}{p}\rfloor\)就可以了。而C++在整数运算除法时，默认就是下取整，这点就不用再特意处理了。
(2)如何计算\(|S_2 \cap S_3|\)这样的的表达式值呢？
题目给定的\(p_i\)都是质数，所以能被2整除，也能被3整除的数，肯定是能被6整除的数，所以就是 \(|S_6|=|S_2 \cap S_3|\),这样，问题就转化成了问题1，也就会求解了！
(3)泛化找到通用公式【顺便讨论一下它的时间复杂度】
\(|S_{p1} \cap S_{p2} \cap S_{p3} \cap ... \cap S_{pm}| = \lfloor \frac{n}{p_1 \times p_2 \times p_3 \times ... \times p_m} \rfloor\)
上式子的时间复杂度是\(O(m)\)的。整体的时间复杂度就是\(O(2^m \times m)\),本题m=16,就是
\(O(2^{16} \times 2^4)\)=65536*16=100W左右。约等于1e7，就是C++一秒可回！这里为什么是\(2^m\)，是因为按2，3，5的倍数进行划分的集合，其实数量是很少的，只有区区3个，也就是说，按容斥原理，运算的时间复杂度是\(O(2^3)\)
(4)怎么样把这些子项目都罗列出来
走到了这一步，容斥原理基本上没有障碍了，因为我们知道公式，还知道公式的第一个子项目怎么求解，是不是可以编码了？嘿嘿，还有最后一个拦路虎：怎么样把这些子项目都罗列出来？而且是要有前面的正负号的，都罗列出来（带着正负号），然后加在一起就是答案了。
我们先来明确：我们要罗列的是什么东西？
就是p[i]的所有组合方式！举个栗子： {2},{3},{5},{2,3},{3,5},{2,5},{2,3,5}共7种,也就是\(2^3-1=7\)种。
如何不重不漏的把这七种可能都遍历到呢？这里使用的是算法竞赛中非常常用的遍历所有可能的方法：二进制遍历！
这里需要注意的是，循环是从1开始的，至 \(2^3-1\)止，为什么不是从零开始呢？因为如果是从零开始，表示的是三个质数一个也不要！这与本题的要求不符，所以排除了零。
那我们如何知道一个数的每一位是不是1呢？
So Easy,我们可以利用位运算知道第k位是不是1呢？ i>> k&1 就是了！
C++ 代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 20;
int p[N]; //p是质数集合，最多有m项，1≤m≤16,我们开了20个，肯定够用了。
int main() {
int n, m; //n个整数，m是质数个数
cin >> n >> m;
//读入了m个质数
for (int i = 0; i < m; i++) cin >> p[i];
//最后的结果
int res = 0;
//不重不漏的遍历所有质数的组合情况，但要排除掉所有质数都不选择的情况，即i>0
for (int i = 1; i < 1 << m; i++) {
int t = 1, cnt = 0; //t代表当前所有质数的乘积,cnt当前选法里面包含几个1,奇数个是相加的，偶数个是相减的
for (int j = 0; j < m; j++) // 遍历pj数组,注意：这里的下标是从0开始的！
if (i >> j & 1) { //这一位是不是1,是1，表示选择了当前位置的质数
cnt++; //多选择了一个集合进行交集运算
//如果质数乘积大于n了，就不用再继续算了。换句话说，这是这种选择法是不符合要求的，这种组合不合法
//举个简单的栗子： p={2,3,5},而n={1,2,3,4,5,6,7,8,9,10}，如果三个质数都选择了，就是30，这对于最大是10的数组来讲是无效的选择法
if ((LL) t * p[j] > n) {
t = -1; //标识为此次质数组合选择无效，不用处理，找下一个组合就行了。
break;
}
t *= p[j]; //质数相乘
}
//这里是在拼容斥原理的公式
if (t != -1) {
if (cnt % 2) res += n / t; //奇数项加,C++的整数除法默认是下取整,不用再关心取整问题
else res -= n / t; //偶数项减
}
}
cout << res << endl;
return 0;
}