小指针
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的交集4、减去1和3的交集5、减去2和3的交集6; -
而图形7,在第一步被计算了三次,在第二步又被减去三次,所以一来一回相当于没有计算7,但是7显然也是红色形状的组成部分,所以最后再加上7,就得到了红色图形的面积。
n个集合的容斥原理
基于上面的分析,我们用 来表示三个圆形的面积,那么对于红色形状的面积就可以表示成如下形式:
「进一步的,如果我们把3个图形扩展到4个图形呢?」
显然可以有如下表示形式:
「再进一步,如果扩展到n个图形呢?」
「更进一步的,把图形推广到集合,也就是说可以用容斥原理来表示给出集合中所有集合的全部并集。」
我们可以把维恩图中的红色区域表示为三个集合的并集,记为: 。把n个集合的并集表示为: 。
根据前文中三个集合、四个集合求并集的表示形式,进而可以推出n个集合求并集的公式:
实际应用
给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。
请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。
举个例子
给出n=10
,两个质数2
和3
,问题是1~10中有几个数能被2和3中至少一个数整除呢?
列举出1~10
,不难发现能被2
或3
整除的有2,3,4,6,8,9,10
,总共7
个数。
如何用容斥原理分析呢?
我们先找到能被2
整除的数的集合,记作
,那么很容易知道
是 {2,4,6,8,10}
。再找到能被3
整除的数的集合,记作
,那么很容易知道
是{3,6,9}
。
用容斥原理就是:
(注意这里的"||"表示集合的个数,而不是绝对值)。
在该问题中,如果用 表示能被 整除的数的集合,那么最终其实就是在求 。
如何能把公式实现出来呢?
首先,要清楚的是,「题目要求,不需要知道每个集合中具体的数是什么,只需要知道每个集合中有多少数(集合的大小)」。显然,集合的大小就是n/pi
,例如:10
中有多少个2
,既10/2=5
;10
中有多少个3
,既10/3=3
。
其次,我们如何知道,这5个数和3个数之间有几个数是有交集的呢?
这里我们就要注意到题目的一个重要条件,既「给出 m 个不同的质数 p1,p2,…,pm」。p
全部是质数,说明「它们的最小公倍数就是他们的乘积」,而他们的交集就是最小公倍数在 n 中的个数。例如:2*3=6
则2和3的最小公倍数就是6,用10/6=1
就找出来了2
和3
的交集的个数。
二进制枚举状态
在本题中,共有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;
}
作者介绍