引言
容斥原理（Inclusion-Exclusion Principle）是组合数学中最基本也最强大的计数工具之一。当我们需要计算满足某些条件的元素个数，而这些条件之间存在重叠时，直接计数往往会导致重复或遗漏。容斥原理通过系统地加减交集的方式，精确地消除了重复计数。本文将用Java实现容斥原理的通用求解框架，并延伸至莫比乌斯反演，帮助读者掌握这类经典组合计数问题的算法实现。
容斥原理的数学基础
给定有限集合 U 和 n 个性质 P₁, P₂, ..., Pₙ，设 Aᵢ 为具有性质 Pᵢ 的元素集合。容斥原理公式为：
|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Aᵢ| - Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| - ... + (-1)^(n+1)|A₁ ∩ ... ∩ Aₙ|
等价地，计算”不具有任何性质”的元素个数：
|U - (A₁ ∪ ... ∪ Aₙ)| = |U| - Σ|Aᵢ| + Σ|Aᵢ ∩ Aⱼ| - ... + (-1)ⁿ|A₁ ∩ ... ∩ Aₙ|
该公式的核心思想是：先粗略减去所有单个集合的大小，再加回被多减的交集，再减去被多加的三重交集，依此类推。
经典问题：与K互质的数的个数
给定正整数 N 和 K，求区间 [1, N] 中与 K 互质（最大公约数为1）的整数个数。
算法思路：
1. 对 K 进行质因数分解，得到所有不同质因子 p₁, p₂, ..., pₘ
2. 使用容斥原理计算能被至少一个质因子整除的数的个数
3. 用总数 N 减去上述结果，即得与 K 互质的数的个数
例如 N = 30, K = 12 = 2² × 3，质因子为 {2, 3}：
– 能被2整除的数：⌊30/2⌋ = 15
– 能被3整除的数：⌊30/3⌋ = 10
– 能被6整除的数：⌊30/6⌋ = 5
– 结果 = 30 – (15 + 10) + 5 = 10
莫比乌斯函数与莫比乌斯反演
莫比乌斯函数 μ(n) 是数论中的重要函数：
μ(n) = 1 若n是无平方因子数且有偶数个质因子
-1 若n是无平方因子数且有奇数个质因子
0 若n含有平方因子
莫比乌斯反演定理：若 F(n) = Σ_{d|n} f(d)，则 f(n) = Σ_{d|n} μ(d) · F(n/d)。
在容斥问题中，莫比乌斯反演提供了更高效的计算方式。对于”与K互质”问题，答案可直接表示为：
ans = Σ_{d|K} μ(d) · ⌊N/d⌋
Java实现
以下实现包含容斥原理的通用框架、质因数分解、以及基于莫比乌斯反演的高效解法：
import java.util.*;
/**
* 容斥原理与莫比乌斯反演的Java实现
* 应用场景：集合计数、互质数统计、子集枚举
*/
public class InclusionExclusion {
// ============ 基础工具方法 ============
// 对n进行质因数分解，返回所有不同的质因子
static List<Long> primeFactors(long n) {
List<Long> factors = new ArrayList<>();
for (long i = 2; i * i <= n; i++) {
if (n % i == 0) {
factors.add(i);
while (n % i == 0) n /= i;
}
}
if (n > 1) factors.add(n);
return factors;
}
// 计算GCD
static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
// ============ 容斥原理：与K互质的数的个数 ============
/**
* 方法1：直接使用容斥原理
* 枚举所有质因子的非空子集，计算能被子集中所有质因子整除的数的个数
*/
static long countCoprimeByIE(long n, long k) {
List<Long> primes = primeFactors(k);
int m = primes.size();
long result = 0;
// 枚举所有非空子集 (用位掩码表示)
for (int mask = 1; mask < (1 << m); mask++) {
long lcm = 1; // 子集中质因子的乘积（因都是质数，乘积即LCM）
int bits = 0; // 子集中元素个数
for (int i = 0; i < m; i++) {
if ((mask & (1 << i)) != 0) {
lcm *= primes.get(i);
bits++;
}
}
// 容斥符号：奇数个元素为减，偶数个元素为加
long count = n / lcm;
if (bits % 2 == 1) result += count;
else result -= count;
}
return n - result; // 总数减去不互质的数
}
// ============ 莫比乌斯函数与反演 ============
// 线性筛法预处理莫比乌斯函数（适用于n不超过MAX_N的情况）
static class MobiusSieve {
int[] mu;
boolean[] isPrime;
List<Integer> primes = new ArrayList<>();
MobiusSieve(int maxN) {
mu = new int[maxN + 1];
isPrime = new boolean[maxN + 1];
Arrays.fill(isPrime, true);
mu[1] = 1;
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= maxN; i++) {
if (isPrime[i]) {
primes.add(i);
mu[i] = -1; // 质数有一个质因子
}
for (int p : primes) {
if (i * p > maxN) break;
isPrime[i * p] = false;
if (i % p == 0) {
mu[i * p] = 0; // 含平方因子
break;
} else {
mu[i * p] = -mu[i]; // 质因子个数奇偶性翻转
}
}
}
}
}
/**
* 方法2：使用莫比乌斯反演（需要预筛）
* ans = Σ_{d|K} μ(d) * floor(N/d)
*/
static long countCoprimeByMobius(long n, long k, MobiusSieve sieve) {
long result = 0;
for (long d = 1; d * d <= k; d++) {
if (k % d == 0) {
// d是k的因数
if (d <= sieve.mu.length - 1) {
result += sieve.mu[(int)d] * (n / d);
}
long d2 = k / d;
if (d2 != d && d2 <= sieve.mu.length - 1) {
result += sieve.mu[(int)d2] * (n / d2);
}
}
}
return result;
}
// ============ 通用容斥框架 ============
/**
* 通用容斥计数器
* 给定n个集合，每个集合用一个 Predicate<T> 表示
* 计算满足"恰好满足k个条件"或"至少满足1个条件"的元素个数
*/
static class InclusionExclusionCounter<T> {
// 计算满足至少一个条件的元素数
int countUnion(List<T> universe, List<java.util.function.Predicate<T>> conditions) {
int n = conditions.size();
int count = 0;
for (int mask = 1; mask < (1 << n); mask++) {
List<java.util.function.Predicate<T>> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) subset.add(conditions.get(i));
}
int satisfy = 0;
for (T elem : universe) {
if (subset.stream().allMatch(p -> p.test(elem))) satisfy++;
}
if (subset.size() % 2 == 1) count += satisfy;
else count -= satisfy;
}
return count;
}
// 计算不满足任何条件的元素数
int countNone(List<T> universe, List<java.util.function.Predicate<T>> conditions) {
return universe.size() - countUnion(universe, conditions);
}
}
// ============ 测试与演示 ============
public static void main(String[] args) {
System.out.println("=== 容斥原理与莫比乌斯反演演示 ===\n");
// 示例1：计算[1, 100]中与60互质的数的个数
long N = 100, K = 60;
System.out.printf("问题：[%d, %d] 中与 %d 互质的数的个数%n", 1L, N, K);
System.out.printf("60的质因子分解: %s%n", primeFactors(K));
long ans1 = countCoprimeByIE(N, K);
System.out.printf("容斥原理结果: %d%n", ans1);
// 验证：暴力枚举
long brute = 0;
for (long i = 1; i <= N; i++) if (gcd(i, K) == 1) brute++;
System.out.printf("暴力验证结果: %d%n", brute);
// 示例2：莫比乌斯反演（预筛到1000）
MobiusSieve sieve = new MobiusSieve(1000);
long ans2 = countCoprimeByMobius(N, K, sieve);
System.out.printf("莫比乌斯反演结果: %d%n\n", ans2);
// 示例3：通用容斥框架
System.out.println("=== 通用容斥框架演示 ===");
List<Integer> universe = Arrays.asList(1,2,3,4,5,6,7,8,9,10);
List<java.util.function.Predicate<Integer>> conds = Arrays.asList(
x -> x % 2 == 0, // 偶数
x -> x % 3 == 0, // 3的倍数
x -> x > 5 // 大于5
);
InclusionExclusionCounter<Integer> counter = new InclusionExclusionCounter<>();
int unionCount = counter.countUnion(universe, conds);
int noneCount = counter.countNone(universe, conds);
System.out.printf(" Universe: %s%n", universe);
System.out.printf(" 条件：偶数 或 3的倍数 或 大于5%n");
System.out.printf(" 满足至少一个条件的元素数: %d%n", unionCount);
System.out.printf(" 不满足任何条件的元素数: %d%n", noneCount);
// 示例4：莫比乌斯函数表
System.out.println("\n=== 莫比乌斯函数表 (1-20) ===");
for (int i = 1; i <= 20; i++) {
System.out.printf(" μ(%d) = %d%n", i, sieve.mu[i]);
}
}
}
关键算法要点解析
位掩码枚举子集：容斥原理需要枚举所有非空子集。当质因子个数 m ≤ 20 时，可使用位掩码 mask（范围 1 到 2^m - 1）高效枚举。mask 的第 i 位为1表示选中第 i 个质因子。
线性筛求莫比乌斯函数：传统方法需要对每个数单独分解质因数，复杂度 O(n√n)。线性筛利用已筛出的质数和莫比乌斯函数的积性，在 O(n) 时间内预处理 1 到 n 的所有莫比乌斯函数值。
积性函数的应用：莫比乌斯函数是积性函数，即当 gcd(a,b)=1 时，μ(ab) = μ(a)μ(b)。这一性质使得线性筛可以递推计算所有值。
复杂度分析
- 容斥原理（质因子分解+子集枚举）：设
K有m个不同质因子，时间复杂度O(√K + 2^m)。当K ≤ 10^12时，m通常不超过12，完全可行。 - 莫比乌斯反演（预筛版）：预处理
O(MAX_N)，单次查询O(√K)（枚举因数）。适用于多组查询场景。 - 通用容斥框架：
O(2^n · |U| · n)，n为条件数。仅适用于小规模问题。
扩展应用
- 欧拉函数计算：
φ(n)可用莫比乌斯反演表示为φ(n) = n · Σ_{d|n} μ(d)/d，这是数论中极为优美的公式。 - 容斥原理在概率中的应用：当事件不独立时，用容斥计算并事件概率：
P(A∪B∪C) = P(A)+P(B)+P(C) - P(A∩B) - P(A∩C) - P(B∩C) + P(A∩B∩C) - 多重约束计数：如”计算1到N中不被2、3、5中任何一个整除的数的个数”，直接应用容斥即可。
