容斥原理的定义以及计算方式

容斥原理是十分有用的一种计算方法，通常用于子集统计中
该原理通过交替加减不同层次交集的大小，确保每个元素在并集中只被计算一次。虽然描述中的“只被两个集合重复的”可能指恰好属于两个集合的元素，但容斥原理实际处理的是所有交集（包含属于更多集合的元素），并通过后续的加减进行修正。
原理：整体减空白的思想，不过也有韦恩图的一点思想，当子集数量大于3时，就有些抽象了，这时我们就需要总结一下规律。
基本公式

$|A_1\cup A_2\cup ··· \cup A_n|=\Sigma|A_i|-\Sigma|A_i\cap A_j|+\Sigma|A_i\cap A_j\cap A_k|+(-1)^{n+1}|A_1\cap A_2 \cap ···\cap A_n|$

先加上所有子集，再减去每两个子集的重叠部分，再加上每三个子集的重叠部分···最后再是所有子集的交集。
重要观察：每一个求和前面的符号只和选择了几个集合有关，所以在写代码的时候就会变得简单了。
代码实现

以题目Count Good Numbers为例：
题目要求我们统计因子里不含2,3,5,7的所有在区间$[l,r]$里的数字总量(翻译成人话)
那么这不就是容斥原理吗？

ll count_divisible(ll l, ll r, ll d) {
    ll first= (l%d==0) ? l : l+d-l%d;  // 第一个能被 d 整除的数
    ll last=r-r%d;                         // 最后一个能被 d 整除的数
    if (first>last) return 0;                 // 如果没有这样的数
    return (last-first)/d+1;
}
void solve(){
    ll l,r;
    cin>>l>>r;
    int primes[]={2,3,5,7};               // 质数数组
    ll ans=0;
    // 枚举所有子集（包括空集），共 2^4 = 16 个
    for(int mask=0;mask<(1<<4);mask++) {
        ll d=1;
        int cnt=0;                           // 子集中质数的个数
        for(int i=0;i<4;i++){
            if(mask&(1<<i)){
                d*=primes[i];
                cnt++;
            }
        }
        // 根据子集大小的奇偶性决定符号
        int sign=(cnt%2==0)?1:-1;
        ans+=sign*count_divisible(l,r,d);
    }
    cout<<ans<<endl;
}

主要思想：用二进制模拟是否要取得这一个集合，然后统计二进制中1出现的次数，即选择的集合数，来决定要加还是减。这样就大大减少了代码量，简单可维护性高。

容斥原理的定义以及计算方式

基本公式

代码实现