HDU 1796How many integers can you find(简单容斥定理)

How many integers can you findTime Limit: 12000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3315 Accepted Submission(s): 937


Problem Description Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N=12, and M-integer set is {2,3}, so there is another set {2,3,4,6,8,9,10}, all the integers of the set can be divided exactly by 2 or 3. As a result, you just output the number 7.
Input There are a lot of cases. For each case, the first line contains two integers N and M. The follow line contains the M integers, and all of them are different from each other. 0<N<2^31,0<M<=10, and the M integer are non-negative and won’t exceed 20.
Output For each case, output the number.
Sample Input

12 22 3

Sample Output

7

Authorwangye
Source2008 “Insigma International Cup” Zhejiang Collegiate Programming Contest - Warm Up（4）

题目大意：很简单的题目，直接看意思就懂哈！
解题思路：容斥定理，加奇减偶，开始忘记求lcm了，！！而且开始还特判0的情况，题目中说的必须是除以，所以0不是一个解。。。开始竟然以为需要是因子就可以了。想通了之后直接先筛选一次，把0都筛选出去。
题目地址：How many integers can you find
AC代码：

#include<iostream>#include<cstring>#include<string>#include<cmath>#include<cstdio>using namespace std;__int64 sum;int n,m;int a[25];int b[25];int visi[25];__int64 gcd(__int64 m,__int64 n){    __int64 tmp;    while(n)    {        tmp=m%n;        m=n;        n=tmp;    }    return m;}__int64 lcm(__int64 m,__int64 n){    return m/gcd(m,n)*n;}void cal(){    int flag=0,i;    __int64 t=1;    __int64 ans;    for(i=0;i<m;i++)    {        if(visi[i])        {            flag++;   //记录用了多少个数            t=lcm(t,b[i]);        }    }    ans=n/t;    if(n%t==0) ans--;    if(flag&1) sum+=ans;   //加奇减偶    else sum-=ans;}int main(){    int i,j,p;    while(~scanf("%d%d",&n,&m))    {        sum=0;        for(i=0;i<m;i++)            scanf("%d",&a[i]);        int tt=0;  //        for(i=0;i<m;i++)        {            if(a[i])  //去掉0                b[tt++]=a[i];        }        m=tt;        p=1<<m;   //p表示选取多少个数，组合数的状态        for(i=1;i<p;i++)        {            int tmp=i;            for(j=0;j<m;j++)            {                visi[j]=tmp&1;                tmp>>=1;            }            cal();        }        printf("%I64d\n",sum);    }    return 0;}/*12 22 312 32 3 012 42 3 2 0*///968MS