HDU 1796 How many integers can you find（容斥）题解

思路：二进制解决容斥问题，就和昨天做的差不多。但是这里题目给的因子不是质因子，所以我们求多个因子相乘时要算最小公倍数。题目所给的因数为非负数，故可能有0，如果因子为0就要删除。

代码：

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 20000 + 10;
const int seed = 131;
const int MOD = 9901;
const int INF = 0x3f3f3f3f;
ll a[100];
ll n, m;
ll gcd(ll aa, ll b){
    return b == 0? aa : gcd(b, aa % b);
}
ll solve(){
    ll ans = 0;
    for(ll i = 1; i < (1 << m); i++){
        int num = 0;
        ll val = 1;
        for(int j = 0; j < m; j++){
            if(i & (1 << j)){
                val = val / gcd(val, a[j]) * a[j];
                num++;
            }
        }
        if(num & 1){
            ans += n / val;
        }
        else{
            ans -= n / val;
        }
    }
    return ans;
}
int main(){
    while(~scanf("%lld%lld", &n, &m)){
        n--;
        for(int i = 0; i < m; i++){
            scanf("%lld", &a[i]);
            if(a[i] == 0){
                i--;
                m--;
            }
        }
        printf("%lld
", solve());
    }
    return 0;
}