莫欺少年穷，修仙之旅在这开始—>算法基础课题解

容斥原理

$\bigcup\limits_{i=1}^nS_i=\sum\limits_{i}S_i-\sum\limits_{i<j}{S_i\cap S_j}+\sum\limits_{i<j<k}{S_i\cap S_j\cap S_k}-…+(-1)^{n-1}\sum\limits_{i<j<k<…}{S_1\cap S_2\cap … S_n}$

证明：

假设元素 $x$ 在 $k$ 个集合中，那么出现次数 $cnt=C_k^1-C_k^2+…+(-1)^{k-1}C_k^k=1$，故等式成立

本题思路：

$00101$ 表示 $5$ 个质数，选择 $p[0]$ 和 $p[2]$ 两个质数，用i >> j & 1的方式可查看是否选择当前位的质数

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 16;

int n,m;
int p[N];

int main()
{
    cin>>n>>m;

    for(int i=0;i<m;i++) cin>>p[i];

    int res=0;
    for(int i=1;i<1<<m;i++)
    {
        // t 表示选择的质数的乘积，cnt 表示选择多少个质数
        int t=1,cnt=0;
        for(int j=0;j<m;j++)
            if(i>>j&1) 
            {
                if((LL)t*p[j]>n) 
                {
                    t=-1;
                    break;
                }
                t*=p[j];
                cnt++;
            }

        if(t!=-1)
        {
            if(cnt%2) res+=n/t;
            else res-=n/t;
        }
    }

    cout<<res<<endl;

    return 0;
}