容斥原理

概念讲解

什么是容斥原理？

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

公式

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

实现

二进制枚举子集

123456789101112131415161718192021222324int inclusionExclusion(vector<int>& sets) {
    int n = sets.size();
    int result = 0;
    
    for (int mask = 1; mask < (1 << n); mask++) {
        int lcm = 1;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                lcm = lcm * sets[i] / gcd(lcm, sets[i]);
                count++;
            }
        }
        
        if (count % 2 == 1) {
            result += n / lcm;
        } else {
            result -= n / lcm;
        }
    }
    
    return result;
}

经典问题

1. 与 n 互质的数的个数

123456789101112131415161718192021222324int countCoprime(int n, vector<int>& primes) {
    int result = 0;
    int m = primes.size();
    
    for (int mask = 1; mask < (1 << m); mask++) {
        int product = 1;
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                product *= primes[i];
                count++;
            }
        }
        
        if (count % 2 == 1) {
            result += n / product;
        } else {
            result -= n / product;
        }
    }
    
    return n - result;
}

2. 错排问题

12345int derangement(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    return (n - 1) * (derangement(n - 1) + derangement(n - 2));
}

考点分析

初赛考查方式

1. 选择题： 容斥原理的概念
2. 程序阅读： 理解容斥原理
3. 编程题： 容斥原理应用

常见题型

• 集合计数
• 互质数计数
• 错排问题

例题精讲

例题 1：与 n 互质的数的个数

题目： 求 [1, n] 内与 n 互质的数的个数。

解答：

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include <iostream>
#include <vector>
using namespace std;

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

int countCoprime(int n, vector<int>& primes) {
    int result = 0;
    int m = primes.size();
    
    for (int mask = 1; mask < (1 << m); mask++) {
        int product = 1;
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                product *= primes[i];
                count++;
            }
        }
        
        if (count % 2 == 1) {
            result += n / product;
        } else {
            result -= n / product;
        }
    }
    
    return n - result;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> primes;
    int temp = n;
    for (int i = 2; i * i <= temp; i++) {
        if (temp % i == 0) {
            primes.push_back(i);
            while (temp % i == 0) {
                temp /= i;
            }
        }
    }
    if (temp > 1) primes.push_back(temp);
    
    cout << countCoprime(n, primes) << endl;
    
    return 0;
}

练习题

1. 洛谷 P1447 能量采集

1234567891011121314151617181920212223242526272829303132333435363738394041#include <iostream>
using namespace std;

const int N = 100005;
int mu[N], prime[N], cnt;
bool isPrime[N];

void init() {
    mu[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!isPrime[i]) {
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for (int j = 0; j < cnt && i * prime[j] < N; j++) {
            isPrime[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
}

int main() {
    init();
    
    int n, m;
    cin >> n >> m;
    
    if (n > m) swap(n, m);
    
    long long ans = 0;
    for (int d = 1; d <= n; d++) {
        ans += (long long)mu[d] * (n / d) * (m / d);
    }
    
    cout << ans << endl;
    return 0;
}

2. 洛谷 P2568 GCD

123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <iostream>
using namespace std;

const int N = 10000005;
int phi[N], prime[N], cnt;
bool isPrime[N];

void init() {
    phi[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!isPrime[i]) {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && i * prime[j] < N; j++) {
            isPrime[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

int main() {
    init();
    
    int n;
    cin >> n;
    
    long long prefix[n + 1];
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + phi[i];
    }
    
    long long ans = 0;
    for (int d = 1; d <= n; d++) {
        ans += 2 * prefix[n / d] - 1;
    }
    
    cout << ans << endl;
    return 0;
}

3. 洛谷 P1390 公约数的和

12345678910111213141516171819202122232425262728293031323334353637383940414243#include <iostream>
using namespace std;

const int N = 2000005;
int phi[N], prime[N], cnt;
bool isPrime[N];

void init() {
    phi[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!isPrime[i]) {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && i * prime[j] < N; j++) {
            isPrime[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

int main() {
    init();
    
    int n;
    cin >> n;
    
    long long ans = 0;
    for (int d = 1; d <= n; d++) {
        long long sum = 0;
        for (int i = d; i <= n; i += d) {
            sum += phi[i / d];
        }
        ans += d * sum;
    }
    
    cout << ans << endl;
    return 0;
}

易错点

⚠️ 注意：

1. 容斥原理要注意符号
2. 二进制枚举子集要从 1 开始
3. LCM 可能溢出
4. 容斥原理是计数的重要工具