定义

容斥原理是一种计数方法，用于计算有限集合的并集的大小。

两个集合

$|A \cup B| = |A| + |B| - |A \cap B|$

三个集合

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

通用公式

对于 $n$ 个集合 $A_1, A_2, \ldots, A_n$：

$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1}|A_1 \cap A_2 \cap \cdots \cap A_n|$

或写为： $\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\emptyset \neq S \subseteq \{1,2,\ldots,n\}} (-1)^{|S|-1}\left|\bigcap_{i \in S} A_i\right|$

具体可用组合恒等式证明

例题

AcWing 890. 能被整除的数

void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (int i = 0; i < m; i++) cin >> a[i];

    int ans = 0;
    for (int i = 1; i < (1 << m); i++) {
        int bt = 0;
        i64 t = 1;
        bool ok = 1;
        for (int j = 0; j < m; j++) {
            if (i >> j & 1) {
                bt++;
                t = lcm(t, a[j]); // 题目保证a[j]为质数，可以用乘
                if (t > n) {
                    ok = 0;
                    break;
                }
            }
        }
        if (!ok) continue;
        if (bt % 2 == 1)
            ans += n / t;
        else
            ans -= n / t;
    }
    cout << ans << "\n";
}