CSP初赛知识精讲--容斥原理

第十三节 容斥原理

基础知识

 在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥除去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
基本计算公式
$|A\cup B|=|A|+|B|-|A\cap B|$
$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$
($A、B、C$为集合，$|A|$表示$A$集合内成员数量，$\cup$运算为并集，$\cap$为交集)

范例精讲

 例1 某班有学生45人，每人在暑假里都参加体育训练队，其中参加足球队的有25人，参加排球队的有22人，参加游泳队的有24人，足球、排球都参加的有12人，足球、游泳都参加的有9人，排球、游泳都参加的有8人，问：三项都参加的有多少人？
 解析：设参加足球队的人数为A，参加排球队的人数为B，参加游泳队的人数为C，三项都参加的人数设为X。带入计算公式：$25+22+24-12-99-8+X=45$，解得$X=3$。

 例2 分母是1001的最简分数一共有多少个？
 解析：此题实际是找分子中不能与1001进行约分的数。由于先对1001质因子分解，可知$1001=7\times 11\times 13$，所以就是找不能被$7、11、13$整除的数。
 在$1$~$1001$中，是$7$的倍数的有$1001/7=143$个；是$11$的倍数的有$1001/11=91$个；是$13$的倍数的有$1001/13=77$个；是$7\times 11$的倍数的有$1001/77=13$个；
是$7\times 13$的倍数的有$1001/91=11$个；是$11\times 13$的倍数的有$1001/143=7$个；是$7\times 11\times 13$的倍数的有$1001/1001=1$个。
 代入容斥原理基本计算公式：能被7或11或13整除的数有$(143+91+77)-(13+11+7)+1=281$个，所以不能被$7、11、13$整除的数有$1001-281=720$个。

赛题训练

1. 一次期末考试，某班有15个数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分得同学有多少人？( )
    A.23 B.21 C.20 D.22
2. 10 000以内，与10 000互质得正整数有( )个。
    A.2000 B.4000 C.6000 D.8000