数学知识：能被整除的数—容斥原理

题目：AcWing 890. 能被整除的数
给定一个整数 n 和 m 个不同的质数 p₁,p₂,…,p_m。

请你求出 1∼n 中能被 p₁,p₂,…,p_m 中的至少一个数整除的整数有多少个。

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

第二行包含 m 个质数。

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

数据范围
1≤m≤16,
1≤n,p_i≤10⁹

输入样例：

10 2
2 3

输出样例：

7

题目分析：
该题用到了容斥原理
首先能被m个不同的质数整除，那么可能就会有1、2、3… m个的情况。
我们使用二进制数来枚举所有情况
用S₁表示只能被一个数整除的集合个数，S₂能被两个数整除的集合个数…
由容斥原理得所有情况为加上奇数个数的集合减去偶数个数的集合。

#include <iostream>

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];
    
    int res=0;
    for(int i=1;i<1<<m;i++) //枚举所有情况
    {
    
        int t=1,s=0; // t表示能被整除的数的乘积，s表示数的个数
        for(int j=0;j<m;j++)
        {
    
            if(i>>j&1) // 如果选取
            {
    
                if((LL)t*p[j]>n) // 如果选取的数大于n
                {
    
                    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;
}