容斥原理与算法实现

作者： 作者的头像   huolong , 时间：2026-09-03 23:35:20 , 所有人可见, 阅读  3

讲义：容斥原理与算法实现——以“幸运数字（厄运数字计数）”为例

一、 问题背景与核心转化

1. 题目回顾

  • 给定：$n$ 个幸运数字 $a_0, a_1, \dots, a_{n-1}$，以及上界 $k$ ($1 \le n \le 20, 0 \le k \le 10^9$)。
  • 定义：正整数 $x$ 是“厄运的”，当且仅当它不是任何一个幸运数字的倍数。
  • 求：在 $[1, k]$ 的范围内，有多少个正整数是厄运的？

2. 正难则反与容斥原理

正面直接统计哪些数不是任何幸运数字的倍数非常困难，因此我们使用“正难则反”的思想： $$\text{厄运数字个数} = k - \text{小于等于 } k \text{ 的正整数中「至少是其中一个幸运数字的倍数」的个数}$$

设 $A_i$ 表示小于等于 $k$ 且是幸运数字 $a_i$ 倍数的集合。我们要找的是所有集合的并集大小： $$\left| \bigcup_{i=0}^{n-1} A_i \right|$$

根据容斥原理（Inclusion-Exclusion Principle）： * 加上所有单个集合的大小（交集大小为 1 个数）。 * 减去所有两两交集的大小。 * 加上所有三个集合交集的大小。 * ……以此类推（奇加偶减）。

多个集合的交集对应的倍数，其基数就是它们最小公倍数（LCM）在 $[1, k]$ 内的倍数个数。即： $$\text{交集大小} = \left\lfloor \frac{k}{\text{lcm}(a_{i_1}, a_{i_2}, \dots)} \right\rfloor$$

由于 $n \le 20$，总共有 $2^n - 1$ 种非空组合。我们可以通过两种经典的方式来实现它：方法一：二进制子集枚举；方法二：递归 + 剪枝（DFS）。

二、 方法一：二进制子集枚举

1. 原理

一个集合有 $n$ 个元素，其所有子集可以用大小从 $1$ 到 $2^n - 1$ 的二进制数来表示。 * 例如当 $n = 3$ 时，二进制数 101（即十进制 5）代表我们选择了第 $0$ 个和第 $2$ 个幸运数字。 * 通过统计每个二进制数中 1 的个数（奇偶性），可以直接决定在容斥原理中是加上还是减去当前组合的贡献。

2. 核心代码实现 (C++11)

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

typedef __int128_t int128; // 防止计算最小公倍数或乘法时溢出
typedef long long ll;

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

// 计算最小公倍数，若溢出或超过 k 则返回 k + 1 触发剪枝
ll lcm(ll a, ll b, ll k) {
    if (a == 0 || b == 0) return 0;
    ll g = gcd(a, b);
    if (a / g > k / b) {
        return k + 1; // 超过上界 k，标记为无效
    }
    return (a / g) * b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll k;
    if (!(cin >> n >> k)) return 0;

    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    ll total_lucky_count = 0;
    int total_subsets = 1 << n; // 2^n 个子集

    // 从 1 枚举到 2^n - 1（不包括空集 0）
    for (int mask = 1; mask < total_subsets; ++mask) {
        ll current_lcm = 1;
        int bits = 0; // 记录当前子集选了几个幸运数字（奇加偶减）
        bool overflow = false;

        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) { // 如果第 i 位为 1，代表选中了 a[i]
                bits++;
                current_lcm = lcm(current_lcm, a[i], k);
                if (current_lcm > k) {
                    overflow = true;
                    break; // 超过 k，该子集贡献为 0，直接跳出
                }
            }
        }

        if (!overflow) {
            ll count = k / current_lcm;
            if (bits % 2 == 1) {
                total_lucky_count += count; // 奇数个集合相交，加上
            } else {
                total_lucky_count -= count; // 偶数个集合相交，减去
            }
        }
    }

    ll unlucky_count = k - total_lucky_count;
    cout << unlucky_count << "\n";

    return 0;
}

三、 方法二：递归 + 剪枝（DFS）

1. 原理

通过深度优先搜索（DFS）遍历每一个幸运数字是“选”还是“不选”。 相比于二进制枚举，递归可以天然地实现强力剪枝： * 在搜索过程中，一旦发现当前的 current_lcm 已经超过了上界 $k$，那么再往后多乘任何数，其最小公倍数也必定大于 $k$，因此其后续的所有子分支可以直接砍掉不搜，极大地节省了时间。

2. 核心代码实现 (C++11)

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

int n;
ll k;
vector<ll> a;
ll total_lucky_count = 0;

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

ll lcm(ll a, ll b) {
    if (a == 0 || b == 0) return 0;
    ll g = gcd(a, b);
    if (a / g > k / b) {
        return k + 1; // 溢出或超过 k 标记
    }
    return (a / g) * b;
}

// DFS 递归函数
// index: 当前考虑第几个幸运数字
// cnt: 当前已经选了几个幸运数字（决定奇偶性）
// current_lcm: 当前组合的最小公倍数
void dfs(int index, int cnt, ll current_lcm) {
    // 剪枝 1：如果当前的最小公倍数已经大于 k，后续不用再选了
    if (current_lcm > k) return;

    // 递归边界：遍历完所有幸运数字
    if (index == n) {
        if (cnt > 0) {
            ll count = k / current_lcm;
            if (cnt % 2 == 1) {
                total_lucky_count += count; // 奇数个相交：加
            } else {
                total_lucky_count -= count; // 偶数个相交：减
            }
        }
        return;
    }

    // 分支 1：不选当前的幸运数字 a[index]
    dfs(index + 1, cnt, current_lcm);

    // 分支 2：选择当前的幸运数字 a[index]
    ll next_lcm = lcm(current_lcm, a[index]);
    dfs(index + 1, cnt + 1, next_lcm);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> k)) return 0;

    a.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 从第 0 个数字开始搜索，初始选了 0 个，当前 lcm 为 1
    dfs(0, 0, 1);

    ll unlucky_count = k - total_lucky_count;
    cout << unlucky_count << "\n";

    return 0;
}

四、 总结与对比

特性 方法一：二进制子集枚举 方法二：递归 + 剪枝 (DFS)
实现直观度 适合 $n$ 较小且确定时，利用循环直接遍历。 结构清晰，逻辑符合回溯思想。
剪枝效率 必须把当前子集所有位算完才能判断是否 > k（除非在循环内加 break）。 极强。一旦 current_lcm > k，整棵子树直接跳过，运行速度更快。
空间复杂度 $O(1)$ $O(n)$（递归栈深度）
适用场景 $n \le 20$ $n \le 20$，且当 $k$ 较小时剪枝优势巨大。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com