[4.9 detailed explanation of inclusion exclusion principle]

$Better\; reading\; experience$

---

thought

• 

• seek $S=S_1\cup S_2\cup S_3$ The area of ：
  $$\begin{array}{rl}It\; can\; be\; seen\; from\; the\; picture\; that: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}$$

• Promotion requirements $S=S_1\cup S_2\cup S_3\cap S_4$ The area of ：
  $$\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}$$

• If we treat area as a set , It is easy to launch ：
  $$\begin{array}{rl}& set\; upUThere\; arenDifferent\; attributes\; ,\; And\; the\; firstiThis\; attribute\; is\; called{P}_{i}Possessing\; attribute{P}_{i}The\; elements\; of\; form\; a\; set{S}_i,that\\ & \\ & \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}\\ & \\ & namely:\\ & \\ & \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}$$

Template example 890. The number divisible

Original link

Given an integer n and m A different prime number p1,p2,…,pm.

Please find out 1∼n Middle energy quilt p1,p2,…,pm How many integers are divided by at least one number in .

Input format
The first line contains integers n and m.

The second line contains m A prime number .

Output format
Output an integer , Represents the number of integers that satisfy the condition .

Data range
1≤m≤16,
1≤n,pi≤109
sample input ：

10 2
2 3

sample output ：

7

Code

#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 These numbers represent 2^m-1 Different items 
        
        LL t=1,s=0;  //s Represents the number of collections contained in the items of the current enumeration  
        
        for(int j=0;j<m;j++){
      // Look at the item  j  Whether the bit contains ,1 The representative contains ,0 Does not include  
            
            if(i>>j&1){
      // choose  
                
                if(t*p[j]>n){
       // here  n/t = 0, direct break that will do  
                    t=-1;
                    break;
                }
                
                t*=p[j];
                s++;
                
            }
            
        }
        
        if(t!=-1){
    
            
            if(s%2) res+=n/t;  // Add the number of odd items  
            else res-=n/t;  // Subtract the number of even items  
            
        }
        
    }
    
    cout<<res<<endl;
    
    return 0;
    
}

---