HDU.1796 How many integers can you find ( 组合数学 容斥原理 二进制枚举)

题意分析

求在[1,n-1]中，m个整数的倍数共有多少个

与 UVA.10325 The Lottery 一模一样。

前置技能和其一样，但是需要注意的有一下几点：

1. m个数字中可能有0

2. 要用long long

代码总览

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#define nmax 20

#define ll __int64

using namespace std;

ll initnum[nmax];

ll n;

int m;

ll gcd(ll a, ll b)

{

    if(!b) return a;

    else return gcd(b, a%b);

}

ll lcm(ll a, ll b)

{

    return a/abs(gcd(a,b))*b;

}

int main()

{

    //freopen("in.txt","r",stdin);

    while(scanf("%I64d %d",&n,&m) != EOF){

        int num  = 0;

        ll temp = 0;

        for(int i = 0 ;i<m;++i){

            scanf("%I64d",&temp);

            if(temp !=0) initnum[num++] = temp;

        }

        ll time  = (1<<num);

        ll ans = 0;

        n--;

        for(int i = 1; i<time;++i){

            int index = 0;

            ll tmpans = 1LL;

            for(int j  = 0; j<num;++j){

                if( 1 & (i>>j)){

                    tmpans = lcm(tmpans,initnum[j]);

                    index++;

                }

            }

            if(index & 1){//add

                ans += n / tmpans;

            }else{//even

                ans -= n / tmpans;

            }

        }

        //ans = n-ans;

        printf("%I64d\n",ans);

    }

    return 0;

}