容斥原理

1、原理

2、代码模板：

#include<iostream>

using namespace std;

const int N=20;
typedef long long ll;

int n,m,p[N];

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)//输入m个质数
        scanf("%d",&p[i]);
    int res=0;//存答案
    for(int i=1;i<1<<m;i++)//按照二进制遍历所有的可能。枚举从1 到 1111...(m个1)的每一个集合状态, (至少选中一个集合)
    {
        int t=1,cnt=0;//t表示选中集合对应质数的乘积,cnt表示选中的集合数量
        for(int j=0;j<m;j++)//遍历0~m位，枚举当前状态的每一位
        {
            if(i>>j&1)//i右移j位，就是判断当前第j位是不是1
            {
                cnt++;//是1的话集合数就+1
                if((ll)t*p[j]>n)//如果乘积大于n,则n/t = 0, 跳出这轮循环
                {
                    t=-1;
                    break;
                }
                t*=p[j];//不大于就更新t
            }
        }
        if(t!=-1)//当不大于n时
        {
            if(cnt%2)   res+=n/t;//集合个数是奇数就加
            else        res-=n/t;//集合个数是偶数就减
        }
    }
    printf("%d",res);
    return 0;
}