How many integers can you find HDU

题意：

给出一个含有 (m) 个数的集合，每个数为不超过 (20) 的非负整数。问 ([1,n)) 中有多少个数满足可以被 (m) 个数中的任意一个整除。

分析：

容斥定理。但又不能直接套，否则会很麻烦。采用子集枚举的方法，特别注意 (0) 的情况。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[15];
int solve(int n,int m)
{
    int res=0;
    for(int i=1;i<=(1<<m)-1;i++)
    {
        int cnt=0,num=1;
        for(int j=0;j<m;j++)
        {
            if((i>>j)&1)
            {
                if(a[j]==0)//注意0
                {
                    cnt=0;
                    break;
                }
                cnt++;
                num=num/__gcd(num,a[j])*a[j];
            }
        }//cout<<"num="<<num<<endl;
        if(cnt&1)
            res+=(n-1)/num;
        else if(cnt>0&&cnt%2==0)
            res-=(n-1)/num;
    }
    return res;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<m;i++)
            scanf("%d",&a[i]);
        printf("%d
",solve(n,m));
    }
    return 0;
}