容斥原理CSP-S

💡 核心思想

容斥原理是计算"至少满足一个条件"或"不满足任何条件"的元素个数的工具。对于两个集合：|A∪B| = |A| + |B| - |A∩B|。对于 n 个集合，公式为：|∪Aᵢ| = Σ|Aᵢ| - Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| - ... + (-1)^{n+1}|∩Aᵢ|。在竞赛中，容斥常用于：计数问题、概率问题、莫比乌斯反演。

🎯 直觉理解

想象你在数班里的同学会打篮球或会游泳的人数。直接数"会打篮球或会游泳"很难，因为有人两项都会。容斥原理说：先数会篮球的，加会游泳的，但两项都会的人被数了两次，所以要减掉一次。这就是容斥的核心：多算了就减，少算了就加。

📝 算法流程

1. 确定 n 个条件/集合
2. 枚举所有非空子集（bitmask 从 1 到 (1<
3. 对于每个子集 S：
4. 计算满足 S 中所有条件的元素个数 cnt(S)
5. 如果 |S| 为奇数，加上 cnt(S)；为偶数，减去 cnt(S)
6. 最终结果为总元素数减去上述容斥结果（或直接用容斥公式）

$$|A_1 \cup A_2 \cup \dots \cup A_n| = \sum_{i} |A_i| - \sum_{i

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// 容斥原理：计算 1~n 中不被任何 p[i] 整除的数的个数
int inclusionExclusion(int n, vector& p) {
    int m = p.size();
    int res = 0;
    for (int mask = 1; mask < (1 << m); mask++) {
        long long lcm = 1;
        int bits = 0;
        for (int i = 0; i < m; i++) {
            if (mask >> i & 1) {
                bits++;
                lcm = lcm / gcd(lcm, (long long)p[i]) * p[i];
                if (lcm > n) break;
            }
        }
        if (lcm > n) continue;
        int cnt = n / lcm;
        if (bits % 2 == 1) res += cnt;
        else res -= cnt;
    }
    return n - res; // 不被任何 p[i] 整除
}

long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }

int main() {
    vector p = {2, 3, 5};
    cout << inclusionExclusion(100, p) << endl; // 100 以内不被 2,3,5 整除的数
    return 0;
}

⚠️ 常见坑点

📚 相关题目