（四）容斥原理

（四）容斥原理

先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

以S1,S2,S3三个集合为例，求出三个集合中包含的元素个数，可以通过韦恩图得到S1∪S2∪S3 = S1+S2+S3- S1∩S2 - S1∩S3 - S2∩S3 + S1∩S2∩S3。通过数学归纳法可以证明，对于求n个集合S1,S2,…,Sn集合中包含的元素个数，可以通过下面的公式来计算（注意正负号交替）：

$$|S_1\cup S_2\cdots \cup S_m|=\sum _i|S_i|-\sum _{i,j}|S_i\cap S_j|+\sum _{i,j,k}|S_i\cap S_j\cap S_k|....+(-1{)}^{n-1}\sum |S_1\cap S_2\cap S_3...\cap S_m|........①$$

计算总共的项数：利用组合数计算，每次从n个元素里面选i个进行交集计算，故总项数

$$C_n^1+C_n^2+\cdots +C_n^n=2^n$$

即时间复杂度为O(2^n)

接下来验证的一下上面①式中每个元素是不是只算了一次(具体证明略)：

$$\begin{gathered} 假设x\in S_1\cup S_2\cdots \cup S_n，存在于k个集合之中，1\le k\le n \\ 那么x被计算的次数为C_k^1-C_k^2+C_k^3-C_k^4+\cdots +(-1{)}^{k-1}{C}_k^k=1 \end{gathered}$$

AcWing 890.能被整除的数

**实现思路：**记Si为1~n中能被pi整除的集合，根据容斥原理，所有数的个数为各个集合的并集，计算公式

$$|S_1\cup S_2\cdots \cup S_m|=\sum _i|S_i|-\sum _{i,j}|S_i\cap S_j|+\sum _{i,j,k}|S_i\cap S_j\cap S_k|....+(-1{)}^{n-1}\sum |S_1\cap S_2\cap S_3...\cap S_m|$$

• 每个集合Si就对应能被质数pi整除的数

• 对于每个集合Si实际上并不需要知道含有哪些元素，只需要知道各个集合中元素个数，对于单个集合Si中元素个数就是对应质数pi的倍数个数（1~n范围内），计算公式为

  $$|S_i|=\frac{n}{p_i}，下取整$$

• 对于任意个集合交集中元素的个数：每个质数pi对应一个集合Si，那么

  $$|S_i\cap S_j|=\frac{n}{p_i\ast p_j}，下取整，即交集就是p_i和p_j的公倍数的个数$$

• 表示每个集合的状态（即选中几个集合的交集，）：m个质数，需要m个二进制位表示，共2^m-1种情况（至少选中一个集合），个数前面的符号为(-1)^(n-1)。以m = 4为例，所以需要4个二进制位来表示每一个集合选中与不选的状态，若此时为1011，表示集合S1∩S3∩S4中元素的个数，同时集合个数为3，前面的符号为(-1)^(3-1)=1，即

  $$|S_1\cap S_3\cap S_4|=(-1{)}^{3-1}\frac{n}{p_1\ast p_3\ast p_4}$$

  怎么取到一个数的每一个二进制位：使用位运算（第一章）, 数i的第j位是否为1：i>>m & 1

  注：用二进制表示状态的小技巧非常常用，后面的状态压缩DP也用到了这个技巧，因此一定要掌握

#include <iostream>
using namespace std;
 
typedef long long LL;
const int N=20;
int p[N];//存储质数pi
int n,m;
 
int mian(){
    cin>>n>>m;
    for(int i=0;i<m;i++) cin>>p[i];
    
    int res=0;
    //枚举各个状态 0000..1到1111..1(m个质数) 至少选中一个集合
    for(int i=1;i<1<<m;i++){//1<<m，即1右移m位 有2^m-1种集合交的情况
        int t=1,s=0;//t表示质数乘积，s表示二进制中1的个数即哪几个质数相乘
        
        //枚举状态的每一位
        for(int j=0;j<m;j++){
            //得到每一个二进制位：位运算
            if(i>>m & 1){
                if((LL)t*p[j]>n){//乘积大于n 元素个数自然为0 跳出该轮循环
                    t=-1;//标记一下
                    break;
                }
                s++;//选中的集合个数
                t=(LL)t*p[j];//乘积
            }
        }
        //得到乘积后
        if(t==-1) continue;
        
        //偶数个集合的交为负 奇数为正
        if(s%2) res+=n/t;
        else res-+n/t;
    }
    cout<<res<<endl;
    return 0;
}