小指针

V1

2022/04/04阅读:47主题:凝夜紫

初中数字之容斥原理及应用

封面原图
封面原图

容斥原理

在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理

维恩图

求著名的维恩图的面积,就是容斥原理的基本应用。

维恩图是如下所示的一种图:

它由三个圆形组成,并且三个圆均存在交集,那么这时候我们如果想求出红色图形的面积,就可以用三个圆的总面积,减去公共面积。

我们给每个部分一个编号,其中1代表黄色圆形、2代表绿色圆形、3代表蓝色圆形、4表示1和2的交集,5表示1和3的交集、6表示2和3的交集、7表示1和2和3三者的交集

那么最外圈的红色形状面积显然是1+2+3-4-5-6+7(数字代表图形面积)就能算出来啦。

用自然语言描述就是:

  1. 先加起来三个圆;
  2. 减去1和2的交集4、减去1和3的交集5、减去2和3的交集6;
  3. 而图形7,在第一步被计算了三次,在第二步又被减去三次,所以一来一回相当于没有计算7,但是7显然也是红色形状的组成部分,所以最后再加上7,就得到了红色图形的面积。

n个集合的容斥原理

基于上面的分析,我们用 来表示三个圆形的面积,那么对于红色形状的面积就可以表示成如下形式:

进一步的,如果我们把3个图形扩展到4个图形呢?

显然可以有如下表示形式:

再进一步,如果扩展到n个图形呢?

更进一步的,把图形推广到集合,也就是说可以用容斥原理来表示给出集合中所有集合的全部并集。

我们可以把维恩图中的红色区域表示为三个集合的并集,记为: 。把n个集合的并集表示为:

根据前文中三个集合、四个集合求并集的表示形式,进而可以推出n个集合求并集的公式:

实际应用

给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。

请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

举个例子

给出n=10,两个质数23,问题是1~10中有几个数能被2和3中至少一个数整除呢?

列举出1~10,不难发现能被23整除的有2,3,4,6,8,9,10,总共7个数。

如何用容斥原理分析呢?

我们先找到能被2整除的数的集合,记作 ,那么很容易知道 {2,4,6,8,10}。再找到能被3整除的数的集合,记作 ,那么很容易知道 {3,6,9}

用容斥原理就是:
(注意这里的"||"表示集合的个数,而不是绝对值)。

在该问题中,如果用 表示能被 整除的数的集合,那么最终其实就是在求

如何能把公式实现出来呢?

首先,要清楚的是,题目要求,不需要知道每个集合中具体的数是什么,只需要知道每个集合中有多少数(集合的大小)。显然,集合的大小就是n/pi,例如:10中有多少个2,既10/2=510中有多少个3,既10/3=3

其次,我们如何知道,这5个数和3个数之间有几个数是有交集的呢?

这里我们就要注意到题目的一个重要条件,既给出 m 个不同的质数 p1,p2,…,pmp全部是质数,说明它们的最小公倍数就是他们的乘积,而他们的交集就是最小公倍数在 n 中的个数。例如:2*3=6则2和3的最小公倍数就是6,用10/6=1就找出来了23的交集的个数。

二进制枚举状态

在本题中,共有m个p,所以会有m个 ,那么我们可以用二进制来枚举出每个集合的状态。

例如,当m=4的时候,需要4个二进制位表示集合,假如当前是1101,则表示选中集合为 (也就是本轮循环需要计算该3个集合)。

用组合数计算枚举的状态总数

如何知道需要枚举多少个二进制位呢?

实我们可以用组合数来表示计算时候每个集合项的选中情况。

第一步中选出所有的集合相加,那么对于某一个集合,共有多少组合项,就是从n个集合中挑出1个,既 ;第二步某两个集合有多少组合项呢?就是从n个集合中挑出2个,既 ,以此类推,最后则是从n个集合中挑出n项,既

最后,即是 。表示的是共有n对组合数,每组组合数都有选或者不选两种情况,而其中 只有一种情况就是全不选,所以只有一种情况,因此最后要减一。

因此,我们需要枚举 个不同的集合状态。

Code

输入样例:
10 2
2 3
输出样例:
7

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 20;

int n, m;
int p[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) cin >> p[i];
    
    int res = 0;
    // 枚举1 到 111...(m个) 中每个集合的状态
    for (int i = 1; i < 1 << m; i ++ ) {
        // t 表示选中集合对应质数的乘积
        // cnt 表示选中集合的数量
        int t = 1, cnt = 0;
        // 枚举当前选法的每一位
        for (int j = 0; j < m; j ++ ) {
            // 1 表示j代表的集合在本轮被选中
            if (i >> j & 1) {
                // 选中集合++
                cnt ++ ;
                // 如果集合中质数的乘积已经大于n,既n/t=0
                // 说明没有交集元素了,所以break掉。
                if ((LL)t * p[j] > n) {
                    t = -1;
                    break;
                }
                t *= p[j];
            }
        }
        if (t != -1) {
            // 如分析 n/t表示交集个数
            // 本轮集合个数是偶数则加上交集,奇数则减去交集
            if (cnt % 2) res += n  / t;
            else res -= n / t;
        }
    }
    cout << res << endl;
    return 0;
}

分类:

数学

标签:

数学编程

作者介绍

小指针
V1