学步园

题意：问1-n范围内（小于n）的数有多少个能够整除一个集合{a，b，……}里任意一个数。

思路：容斥原理的模板题，直接上模板了。

题目

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
#define LL long long
int len,num[20];
LL n,sum;
LL gcd(LL x,LL y)
{
    return x%y?gcd(y,x%y):y;
}
void dfs(LL ans,int sta,int cnt)
{
    ans=ans*num[sta]/gcd(ans,num[sta]);          //求集合前面几个数的最小公倍数
    if(cnt&1)sum+=n/ans;
    else sum-=n/ans;          //这里减去重复计算的数，这时整个代码的精华
    for(int i=sta+1;i<len;i++)dfs(ans,i,cnt+1);
}
int main()
{
    //freopen("a.txt","r",stdin);
    int m;
    while(scanf("%lld%d",&n,&m)!=EOF)
    {
        len=0;
        for(int i=0;i<m;i++)
        {
            int x;
            scanf("%d",&x);
            if(x==0)continue;
            num[len++]=x;
        }
        n--;
        sum=0;
        for(int i=0;i<len;i++)dfs(num[i],i,1);
        printf("%lld\n",sum);
    }
}