描述

容斥原理的简单描述如下：

要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。简单的说，就是对所有单个集合求和后减去单数个集合相交部分，加上双数集合相交部分。

原理公式:

$|\bigcup A_i|=\sum_{1\leq i \leq m} |A_i|-\sum_{1\leq i \leq j \leq m} |A_i \cap A_j|+\sum_{1\leq i \leq j \leq k \leq m} |A_i \cap A_j \cap A_k|- \cdots +(-1)^{m+1} \sum |A_1 \cap A_2 \cap A_3 \cap A_4\cdots\cap A_m|$

例题

给定$a_1,a_2,a_3,\cdots ,a_m$ ，求1到n的整数中至少能整除a中一个元素有几个？

代码：

include <iostream>

using namespace std;

int a[4] = {2,3,5,7};
int n = 100,m = 4;

typedef long long ll;
ll gcd(ll a,ll b){
    ll t;
    if (!a || !b)return 0;
    if (a < b){t = b; b = a; a = t;}
    while (b != 0 ){ t = a % b; a = b; b = t;}
    return a;
}
void solve(){
    ll res = 0;
    for (int i = 1; i < (1 << m); i++){
        int num = 0;
        for(int j = i;j != 0; j >>= 1)
            num += j & 1;
        ll lcm = 1;
        for (int j = 0; j < m; j++){
            if (i >> j & 1){
                lcm = lcm /gcd(lcm,a[j]) * a[j];
                if (lcm > n) break;
            }
        }
        if (num % 2 == 0) res -= n /lcm;
        else res += n / lcm;
        cout << res <<endl;
    }
    cout << res <<endl;
}

int main()
{
    solve();
    return 0;
}