【4.9 容斥原理详解】

$更好的阅读体验$

---

思想

• 

• 求$S=S_1\cup S_2\cup S_3$的面积：
  $$\begin{array}{rl}由图可知:S=& S_1\cup S_2\cup S_3\\ =& S_1+S_2+S_3\\ & -S_1\cap S_2-S_1\cap S_3-S_2\cap S_3\\ & +S_1\cap S_2\cap S_3\end{array}$$

• 推广求$S=S_1\cup S_2\cup S_3\cap S_4$的面积：
  $$\begin{array}{rl}S=& S_1\cup S_2\cup S_3\cap S_4\\ =& S_1+S_2+S_3+S_4\\ & -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_1\cap S_3\cap S_4+S_2\cap S_3\cap S_4\\ & -S_1\cap S_2\cap S_3\cap S_4\end{array}$$

• 若将面积作为集合看待，则容易推出：
  $$\begin{array}{rl}& 设U中元素有n种不同的属性，而第i种属性称为P_i拥有属性P_i的元素构成集合S_i,那么\\ & \\ & \begin{array}{rl}\left|\bigcup _{i=1}^n{S}_i\right|=& \sum _i|S_i|-\sum _{i<j}|S_i\cap S_j|+\sum _{i<j<k}|S_i\cap S_j\cap S_k|-\dots \\ & +(-1{)}^{m-1}\sum _{a_i<a_{i+1}}|\bigcap _{i=1}^m{S}_{a_i}|+\cdots +(-1{)}^{n-1}|S_1\cap \cdots \cap S_n|\end{array}\\ & \\ & 即:\\ & \\ & \left|\bigcup _{i=1}^n{S}_i\right|=\sum _{m=1}^n(-1{)}^{m-1}\sum _{a_i<a_{i+1}}|\bigcap _{i=1}^m{S}_{a_i}|\end{array}$$

模板例题 890. 能被整除的数

原题链接

给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。

请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

输入格式
第一行包含整数 n 和 m。

第二行包含 m 个质数。

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

数据范围
1≤m≤16,
1≤n,pi≤109
输入样例：

10 2
2 3

输出样例：

7

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=20;

int p[N];

int main(){
    
    
    int n,m;
    
    cin>>n>>m;
    
    for(int i=0;i<m;i++) cin>>p[i];
    
    LL res=0;
    
    for(int i=1;i<1<<m;i++){
      // 1~2^m-1这些数代表2^m-1个不同的项
        
        LL t=1,s=0;  //s代表当前枚举的项中包含集合的个数 
        
        for(int j=0;j<m;j++){
      //看这个项的第 j 位是否包含，1代表包含，0代表不包含 
            
            if(i>>j&1){
      //选 
                
                if(t*p[j]>n){
       //此时 n/t = 0，直接break即可 
                    t=-1;
                    break;
                }
                
                t*=p[j];
                s++;
                
            }
            
        }
        
        if(t!=-1){
    
            
            if(s%2) res+=n/t;  //加奇数项的个数 
            else res-=n/t;  //减偶数项的个数 
            
        }
        
    }
    
    cout<<res<<endl;
    
    return 0;
    
}

---