容斥原理

求几个有交集集合的并集

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
int n,m;
int a[20];
int res;

int main(){
    cin >> n >> m;

    for(int i = 0; i < m; i ++) cin >> a[i];

    for(int i = 1; i < 1 << m; i ++){  //二进制枚举，注意枚举的是m（很常用）
        int t = 1, cnt = 0;
        for(int j = 0; j < m; j ++){
            if(i >> j & 1){
                if((LL)t * a[j] > n){ // 这一步的目的是当所选集合的最小公倍数超过n时，说明n/t==0,就没必要计算了
                本质是剪枝。
                    t = -1;
                    break;
                }
                cnt ++;
                t *= a[j];
            }
        }
        if(t == - 1) continue;
        else {
            if(cnt % 2 == 0) res -= n/t; //如果集合数量为偶数个，需要减去
            else res += n/t;//如果集合数量为奇数个，需要加上
        }
    }
    cout << res << endl;
    return 0;
}