ZOJ 2386 容斥原理

题意：给出n个数，和m（1<=m<=200 000 000），求1~M中能被这n个数其中任意一个数整除的个数；

分析：n范围很小，可以枚举选择被哪些数整除，被奇数个整数整除加m/这个n个数的公共最小公倍数；

#include <bits/stdc++.h>

using namespace std;
int n,m,a[15];
int gcd (int a,int b) {
    return b==0? a:gcd(b,a%b);
}

int lcm(int a,int b) {
    return a*b/gcd(a,b);
}

int multiple(int x,int* cnt) {
    int res = 1;
    *cnt = 0;
    for(int i=0;i<n;i++) {
        if(x&(1<<i)) {
            (*cnt)++;
            res = lcm(res,a[i]);
        }
    }
    return res;
}

int main()
{

    while(scanf("%d%d",&n,&m)!=EOF) {
        int ans = 0;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        int k;
        for(int i=1;i<(1<<n);i++) {
            int lcms = multiple(i,&k);
            if(k&1) ans+= m/lcms;
            else ans-=m/lcms;
        }
        printf("%d
",ans);
    }

    return 0;
}