集合问题（容斥原理）7丨三者集合数论问题（仅考查一次）
模拟卷1
1到1000这1000个正整数中，能够被3整除，或能够被5整除，或能够被7整除的数有多少个？
模板解析：A中能被3整除的数有333个，它的元素的个数|A3|=333（333×3+1）同理：|A5|=200, |A7|=142;
|A3∩A5|=66（1000=66×15+10）; |A3∩A7|=47（1000=47×21+13）；
|A5∩A7|=28（1000=28×35+20）。
|A3∩A5∩A7|=9（（1000=9×105+55）
|A3∪A5∪A7|= |A3|+|A5|+|A7|- |A3∩A5| - |A3∩A7| - |A5∩A7|+|A3∩A5∩A7|
= 333+200+142-66-47-28+9= 543
模拟卷2
分母是1001的最简分数一共有多少个？
模板解析：|A7|=143，|A11|=91，|13|=77；
|A7∩A11|=13，|A7∩A13|=11,|A11∩A13|=7;
| A7∩A11∩A13|=1
故而：由容斥原理知：在1~1001中，能被7或11或13整除的数有（143+91+77）-（13+11+7）+1=281（个），从而不能被7、11或13整除的数有1001-281=720（个）.也就是说，分母为1001的最简分数有720个。2016年山东
64.团体操表演中，编号为1~100的学生按顺序排成一列纵队，编号为1的学生拿着红、黄、蓝三种颜色的旗帜，以后每隔2个学生有1人拿红旗，每隔3个学生有1人拿蓝旗，每隔6个学生有1人拿黄旗。问所有学生中有多少人拿两种颜色以上的旗帜？
A.13
B.14
C.15
D.16
【朱建国解析】B。集合问题。
1
三集合容斥原理 华图教育梁维维 我们知道容斥原理的本质是把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复的一种计数的方法。之前我们叙述过了两集合容斥原理，下面我们来看一下三集合容斥原理，相对于两集合容斥原理而言，三集合容斥原理的难度有所增加，但总体难度适中，所以三集合容斥原理在国家公务员考试中出现的频率较高，在其他省份考试以及各省份联考当中也时有出现，下面我们了解一下三集合容斥原理的公式。 三集合容斥原理公式： 三者都不满足的个数。 总个数- = + - - - + + =| | | | | | | | | | | | | || |C B A C B C A B A C B A C B A 有些问题，可以直接代入三集合容斥原理的公式进行求解。 【例1】如图所示，X、Y、Z分别是面积为64、180、160的三张不同形状的纸片。它们部分重叠放在一起盖在桌面上，总共盖住的面积为290。且X与Y、Y与Z、Z与X重叠部分面积分别为24、70、36。问阴影部分的面积是多少?( ) A.15 B.16 C.14 D.18 【解析】依题意，假设阴影部分的面积为x，代入公式可得：64＋180＋160－24－70－36＋x=290，解得x=16，正确答案为B选项。 近几年，直接套用三集合公式的题目有所减少，开始出现条件变形的题目，往往告诉大家“只满足两个条件的共有多少”这样的信息，看似无法直接套用公式，其实只要掌握本质，仍然可以直接套用公式。 【例2】（2012河北-44）某通讯公司对3542个上网客户的上网方式进行调查，其中1258个客户使用手机上网，1852个客户使用有线网络上网，932个客户使用无线网络上网。如果使用不只一种上网方式的有352个客户，那么三种上网方式都使用的客户有多少个?（） A. 148 B. 248
1. 了解容斥原理二量重叠和三量重叠的内容； 2. 掌握容斥原理的在组合计数等各个方面的应用． 一、两量重叠问题 在一些计数问题中，经常遇到有关集合元素个数的计算．求两个集合并集的元素的个数，不能简单地把两个集合的元素个数相加，而要从两个集合个数之和中减去重复计算的元素个数，即减去交集的元素个数，用式子可表示成：A B A B A B =+-(其中符号“”读作“并”，相当于中文“和”或者“或”的意思；符号“”读作“交”，相当于中文“且”的意思．)则称这一公式为包含与排除原理，简称容斥原理．图示如下:A 表示小圆部分，B 表示大圆部分，C 表示大圆与小圆的公共部分，记为：A B ，即阴影面积．图示如下:A 表示小圆部分，B 表示大圆部分， C 表示大圆与小圆的公共部分，记为：A B ，即阴影面积． 包含与排除原理告诉我们，要计算两个集合A B 、的并集A B 的元素的个数，可分以下两步进行： 第一步：分别计算集合A B 、的元素个数，然后加起来，即先求A B +(意思是把A B 、的一切元素都“包含”进 来，加在一起)； 第二步：从上面的和中减去交集的元素个数，即减去C A B =(意思是“排除”了重复计算的元素个数)． 二、三量重叠问题 A 类、 B 类与 C 类元素个数的总和A =类元素的个数B +类元素个数C +类元素个数-既是A 类又是B 类的元素个数-既是B 类又是C 类的元素个数-既是A 类又是C 类的元素个数+同时是A 类、B 类、C 类的元素个数．用符号表示为：A B C A B C A B B C A C A B C =++---+．图示如下： 教学目标 知识要点 7-7-5.容斥原理之最值问题 1．先包含——A B + 重叠部分A B 计算了2次，多加了1次； 图中小圆表示A 的元素的个数，中圆表示B 的元素的个数， 1．先包含：A B C ++ 重叠部分A B 、B C 、C A 重叠了2次， 多加了1次． 2．再排除：A B C A B B C A C ++---
几何学基础简介 Lex Li 几何原本简介 古希腊大数学家欧几里德是与他的巨著——《几何原本》一起名垂千古的。这本书是世界上最著名、最完整而且流传最广的数学著作，也是欧几里德最有价值的一部著作。欧几里德把人们公认的一些事实列成定义和公理，以形式逻辑的方法，用这些定义和公理来研究各种几何图形的性质，从而建立了一套从公理、定义出发，论证命题得到定理得几何学论证方法，形成了一个严密的逻辑体系——几何学。而这本书，也就成了欧式几何的奠基之作。 作为基础的五条公理和公设 五条公理 1.等于同量的量彼此相等； 2.等量加等量，其和相等； 3.等量减等量，其差相等； 4.彼此能重合的物体是全等的； 5.整体大于部分。 五条公设 1.过两点能作且只能作一直线； 2.线段(有限直线)可以无限地延长； 3.以任一点为圆心,任意长为半径,可作一圆； 4.凡是直角都相等； 5.同平面内一条直线和另外两条直线相交，若在直线同侧的两个内角之和小于180°，则这两条直线经无限延长后在这一侧一定相交。 《几何原本》的主要内容 欧几里得的《几何原本》共有十三卷。 目录 第一卷几何基础 第二卷几何与代数 第三卷圆与角 第四卷圆与正多边形 第五卷比例
第六卷相似 第七卷数论（一） 第八卷数论（二） 第九卷数论（三） 第十卷无理量 第十一卷立体几何 第十二卷立体的测量 第十三卷建正多面体 各卷简介 第一卷：几何基础。重点内容有三角形全等的条件，三角形边和角的大小关系，平行线理论，三角形和多角形等积（面积相等）的条件，第一卷最后两个命题是毕达哥拉斯定理的正逆定理； 第二卷：几何与代数。讲如何把三角形变成等积的正方形；其中12、13命题相当于余弦定理。 第三卷：本卷阐述圆，弦，切线，割线，圆心角，圆周角的一些定理。 第四卷：讨论圆内接和外切多边形的做法和性质； 第五卷：讨论比例理论，多数是继承自欧多克斯的比例理论,被认为是"最重要的数学杰作之一" 第六卷：讲相似多边形理论，并以此阐述了比例的性质。 第五、第七、第八、第九、第十卷：讲述比例和算术的理论；第十卷是篇幅最大的一卷，主要讨论无理量（与给定的量不可通约的量），其中第一命题是极限思想的雏形。 第十一卷、十二、十三卷：最后讲述立体几何的内容. 从这些内容可以看出，目前属于中学课程里的初等几何的主要内容已经完全包含在《几何原本》里了。因此长期以来，人们都认为《几何原本》是两千多年来传播几何知识的标准教科书。 《几何原本》的意义和影响 在几何学发展的历史中，欧几里得的《几何原本》起了重大的历史作用。这种作用归结到一点，就是提出了几何学的“根据”和它的逻辑结构的问题。在他写的《几何原本》中，就是用逻辑的链子由此及彼的展开全部几何学，这项工作，前人未曾作到。《几何原本》的诞生，标志着几何学已成为一个有着比较严密的理论系统和科学方法的学科。 论证方法上的影响 关于几何论证的方法，欧几里得提出了分析法、综合法和归谬法。所谓分析法就是先假设所要求的已经得到了，分析这时候成立的条件，由此达到证明的步骤；综合法是从以前证明过的事实开始，逐步的导出要证明的事项；归谬法是在保留命题的假设下，否定结论，从结论的反面出发，由此导出和已证明过的事实相矛盾或和已知条件相矛盾的结果，从而证实原来命题的结论是正确的，也称作反证法。
容斥原理的极值问题文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208]
有关容斥原理的极值问题 所谓“极值问题”就是通常说的最大值，最小值的问题，题干中通常有“至少”，“至多”等题眼，解决这类问题通常有两种方法，一是极限思想，另一种就是逆向思维。 通过以下几个例题具体看一下： 1. 某社团共有46人，其中35人爱好戏剧，30人爱好体育，38人爱好写作，40人爱好收藏，至少有几个4个活动都参加 解析: 逆向思维，分别考虑不喜欢其中某项活动的人数是多少，由题意可知，分别为11,16,8,6，只有当这四项集合互相没有交集的时候，四项活动都喜欢的人数才最少，因此最少人数为46-11-16-8-6=5 2. 参加某部门招聘考试的共有120人，考试内容共有6道题。1至6道题分别有86人，88人，92人，76人，72人和70人答对，如果答对3道题或3道以上的人员能通过考试，那么至少有多少人能通过考试 解析（极限思想）：要使通过的人最少，那么就是对1道，2道的人最多，并且应该是对2道的人最多（这样消耗的总题目数最多），假设都只对了2道，那120人总共对了240道，而现在对了86+88+92+76+72+70=484，比240多了244道，每个人还可以多4道（这样总人数最少）,244/4=61。(逆向思维)：先算出来1-6题每题错的人数120-86=34 120-88=32 120- 92=28 120-76=44 120-72=48 120-70=50 要使通过的人数最少，就是没通过的人数最多，让错的人都只错4道就错的人最多，总的错的题数为 34+32+28+44+48+50=236236/4=59120-59=61
三集合容斥原理按题型可以分为两种题型，一种为标准型公式，另一种为变异型公式，接下来，我们就着重看看三集合容斥原理的标准型公式。 集合Ⅰ、Ⅱ、Ⅲ，满足标准型公式： 三集合容斥原理标准型公式：Ⅰ+Ⅱ+Ⅲ-Ⅰ·Ⅱ-Ⅰ·Ⅲ-Ⅱ·Ⅲ+Ⅰ·Ⅱ·Ⅲ=总个数-三者都不满足个数 通过观察公式，我们可以看到在公式中，出现了9个量，而这个式子的适用前提就是知8求1，即在题目中，若我们看到了8个已知量，要求1个未知量的时候，就要使用这个公式(注：而题目中有时候也是知7求1，其中的三者都不满足的个数可能为零)，具体题目如下： (陕西2015)针对100名旅游爱好者进行调查发现，28人喜欢泰山，30人喜欢华山，42人喜欢黄山，8人既喜欢黄山又喜欢华山，10人既喜
欢泰山又喜欢黄山，5人既喜欢华山又喜欢黄山，3人喜欢这三个景点，则不喜欢这三个景点中任何一个的有( )人。 A.20 B.18 C.17 D.15 E.14 F.13 G.12 H.10 解：通过观察，我们发现了八个已知量，还要我们求另一个未知量，故可以用上述公式，我们将数据逐个代入可得： 28+30+42-8-10-5+3=100-x，其中x为我们要求的量，求得x=20，答案选择A。 接着，我们来看一下三集合变异型的公式，如下图示：
从上式中，我们可以看出，要使用变异型公式，题目中必须要出现仅满足2个情况的个数，这就是与标准型公式最大的不同，下面我们就看看具体的题目： (广东2015)某乡镇举行运动会，共有长跑、跳远和短跑三个项目。参加长跑的有49人，参加跳远的有36人，参加短跑的有28人，只参加其中两个项目的有13人，参加全部项目的有9人。那么参加该次运动会的总人数为( )。 A.75 B.82 C.88 D.95 解：由于题目中出现“只参加其中两个项目的有13人”，故使用变异型公式，得到下面列式：49+36+28-1×13-2×9=x，通过尾数法(若题目中选项的尾数都不一样的话，就可以用尾数法快速得到答案)，判断出答案为82，选B。 但是，现在变异型公式也出现一些变形的形式，例如国考2015中的这道三集合容斥原理，就给我带来了一写在解题是需要着重注意的地方，下面我们仔细分析一下题目 (国家2015)某企业调查用户从网络获取信息的习惯，问卷回收率为90%。调查对象中有179人使用搜索引擎获取信息，146人从官方网站获取信息，246人从社交网络获取信息，同时使用这三种方式的有115人，使用其中两种的有24人，另有52人这三种方式都不使用，问这次调查共发出了多少份问卷?( ) A.310 B.360
初等数论简介 绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。 1． 请看下面的例子： （1） 证明：对于同样的整数x 和y ，表达式2x+3y 和9x+5y 能同时被整除。(1894年首届匈牙利 数学竞 赛第一题) （2） ①设n Z ∈，证明213 1n -是168的倍数。 ②具有什么性质的自然数n ，能使123n ++++ 能整除123n ??? ？（1956年上海首届数学竞赛第一题） （3） 证明：3 231 122 n n n + +-对于任何正整数n 都是整数，且用3除时余2。（1956年北京、天津市首届数学竞赛第一题） （4） 证明：对任何自然数n ，分数 214 143 n n ++不可约简。（1956年首届国际数学奥林匹克竞赛第一题） （5） 令(,,,)a b g 和[,,,]a b g 分别表示正整数,,,a b g 的最大公因数和最小公倍数，试证： [][][][]()()()() 2 2 ,,,,,,,,,,a b c a b c a b b c c a a b b c c a =??（1972年美国首届奥林匹克数学竞赛第一题） 这些例子说明历来数论题在命题者心目中首当其冲。 2.再看以下统计数字： （1）世界上历史最悠久的匈牙利数学竞赛，从1894~1974年的222个试题中，数论题有41题，占18.5%。 （2）世界上规模最大、规格最高的IMO （国际数学奥林匹克竞赛）的前20届120道试题中有数论13题，占10.8% 。 这说明：数论题在命题者心目中总是占有一定的分量。如果将有一定“数论味”的计数型题目统计在内，那么比例还会高很多。 3.请看近年来国内外重大竞赛中出现的数论题： (1)方程323652x x x y y ++=-+的整数解(,)x y 的个数是（ ） A 、 0 B 、1 C 、3 D 、无穷多 （2007全国初中联赛5） （2）已知,a b 都是正整数，试问关于x 的方程()2 1 02 x abx a b -++=是否有两个整数解？ 如果有，请把它们求出来；如果没有，请给出证明。 （2007全国初中联赛12）
国家公务员| 事业单位| 村官| 选调生| 教师招聘| 银行招聘| 信用社| 乡镇公务员| 各省公务员|政法干警| 招警| 军转干| 党政公选| 法检系统| 路转税| 社会工作师 三集合非标准型容斥原理 ———————————————海南华图数资老师，胡军亮近些年考试经常出现容斥原理的题型，容斥原理分为两集合型跟三集合型，三集合容斥原理又包括标准型和非标准型，三集合容斥原理与三集合标准型容斥原理都是相对好掌握的。这里给大家讲解三集合非标准型容斥原理题的解题方法。首先看下面三个公式 （1） 都不满足 总数- ) (= + + + - + +C B A C A C B B A C B A （2）三条件都不满足 总数 只满足两条件- * 2 -= - + +C B A C B A （3）满足三条件 只满足两条件 只满足一个条件* 3 * 2+ + = + +C B A 公式（1）是标准型公式，公式（2）、（3）都是非标准型公式。 【例1】某乡镇对集贸市场36种食品进行检查，发现超过保质期的7种，防腐添加剂不合格的9种，产品外包装标识不规范的6种。其中，两项同时不合格的5种，三项同时不合格的2种。问三项全部合格的食品有多少种?（） A. 14 B. 21 C. 23 D. 32 解析：该题目为典型的容斥原理题，但是题目提到“两项同时不合格的有5种”，这句话的意思就是只满足两个条件的数量是5，该题属于三集合容斥原理非标准型题，带入公式（2）得到： 7+9+6-5-2*2=36-X，尾数法知道答案选C。 【例2】某市对52种建筑防水卷材产品进行质量抽检，其中有8种产品的低温柔度不合格，10种产品的可溶物含量不达标，9种产品的接缝剪切性能不合格，同时两项不合格的有7种，有1种产品这三项都不合格。则只有一项不合格的建筑防水卷材产品有多少种？ A. 17 B. 12 C. 15 D. 20 解析：该题涉及到只满足一项不合格、同时两项不合格、三项都不合格，属于三个集合非标准型容斥原理的题，带入公式（3）得到： 8+10+9=X+2*7+1，尾数法知道答案选B。 从上面的两道例题的讲解可以看到三集合非标准型容斥原理虽然不是很好理解，但是记住题型的特征，用正确的公式直接套用来解题还是很容易掌握的。
欧几里得算法 欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a,d|b，而r = a - kb，因此d|r 因此d也是（b,a mod b）的公约数 因此（a,b）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，得证欧几里得算法模板 int gcd(int n,int m) { int t,r; if(n
2014年公务员行测：巧解三集合容斥原理问题 华图教育 三集合容斥原理此类题型主要出现在近年来各省的省考中，主要是有三个独立的个体，此类题型主要的做题方法是公式法和作图法。近年来直接套用三集合公式的题目有所减少，开始出现条件变形的题目，不管容斥原理的题目怎么变化，但我们只要掌握住核心思想——剔除重复，那么做任何一个容斥原理题目都能够得心应手。 根据上图，可得三集合容斥原理核心公式： =A +B +C -A B -B C -A C +A B C =-x A B C 总数 一、直接利用公式型 【例1】（2012年4月联考）某公司招聘员工，按规定每人至多可投考两个职位，结果共42人报名，甲、乙、丙三个职位报名人数分别是22人、16人、25人，其中同时报甲、乙职位的人数为8人，同时报甲、丙职位的人数为6人，那么同时报乙、丙职位的人数为： A. 7人 B. 8人 C. 5人 D. 6人 【答案】A 【解析】设同时报乙、丙职位的人数为x ，则根据三集合容斥原理公式有：22+16+25-8-6-x+0=42-0，解得x=7。因此，本题答案为A 选项。 二、三集合容斥原理作图型 若在题目中任何一个位置看到“只满足”或“仅满足”，则公式法不能够再用，采用作图法来解题，注意，在作图的时候不管三七二十一，先画三个两两相交的圈，再往里填数字即可，填的时候注意从中间往外一层一层填。 【例2】（2007年江苏）一次运动会上，17名游泳运动员中，有8名参加了仰泳，有10 C x B A
名参加蛙泳，有12名参加了自由泳，有4名既参加仰泳又参加蛙泳，有6名既参加蛙泳又参加自由泳，有5名既参加仰泳又参加自由泳，有2名这3个项目都参加，这17名游泳运动员中，只参加1个项目的人有多少？（） A.5名 B.6名 C.7名 D.4名 【答案】B 【解析】本题问题中出现了“只”，故只能采用作图法。于是有 仰 1 2 2 2 3 4 3 蛙自由 只参加1个项目的人数为1+2+3=6。因此，本题答案为B选项。 【例3】（2012年河北）某乡镇对集贸市场36种食品进行检查，发现超过保持期的7种，防腐添加剂不合格的9种，产品外包装标识不规范的6种。其中，两项同时不合格的5种，三项同时不合格的2种。问三项全部合格的食品有多少种？（） A.14 B.21 C.23 D.32 【答案】C 【解析】 a d b c 其中d为三项同时不合格的部分，a+b+c为两项同时不合格的部分。设三项全部合格的食品有x种。根据题意有：36-x=7+9+6-5-2×2，解得x=23。因此，本题答案为C选项。 【注】该题注意，由于7+6+9这部分把三项同时不合格的部分共加了3次，减去5的
“4-6 初等数论初步”简介 北京师范大学胡永建 初等数论是研究整数的性质和不定方程（组）的整数解的一门学问，它与几何学是最古老的两个数学分支。初等数论中至今仍有许多没有解决的问题，如哥德巴赫（Goldbach）问题，孪生素数猜想，奇完全数的存在性问题等，它们对人类智慧产生了极大挑战。人们在解决一些初等数论问题的过程中所作的贡献，对数论乃至整个数学的发展起了重要的推动作用，产生了一些直接与数学有关的新的重要数学分支。初等数论在计算机科学和信息工程中有许多重大的实际应用。在本专题中，同学们将通过具体的问题，学习初等数论的一些基本知识，如有关整数和整除的知识，用辗转相除法求解一次同余方程（组）和简单的一次不定方程等，初等数论中蕴含的一些思想方法，以及我国古代数学在初等数论的研究方面取得的一些重要成就。 一、内容与课程学习目标 本专题的学习初等数论的一些基本知识，具体包括：整数的整除、同余与同余方程、一次不定方程和数论在密码中的应用四部分内容。通过本专题的学习，要引导学生：1．通过实例，认识带余除法，理解同余和剩余类的概念及意义，探索剩余类的运算性质（加法和乘法），并且理解它的实际意义。体会剩余类运算与传统数的运算的异同（会出现零因子）。 2．理解整除、因数和素数的概念，了解确定素数的方法,如埃拉托斯特尼（Eratoshenes）筛法，知道素数有无穷多个。 3．了解十进制表示的整数的整除判别法，探索整数能被3，9，11，7等整除的判别法。会检查整数加法、乘法运算错误的一种方法,如弃九验算法。 4．通过实例，探索利用辗转相除法求两个整数的最大公约数的方法，理解互素的概念，并能用辗转相除法证明：若a能整除bc，且a,b互素，则a能整除c。探索公因数和公倍数的性质。了解算术基本定理。 5．通过实例，理解一次不定方程的模型，利用辗转相除法求解简单的一次不定方程。并尝试写出算法的程序框图，在条件允许的情况下上机实现。 6．通过实例（如物不知其数问题），理解一次同余方程组的模型。 7．理解大衍求一术和孙子定理的证明。 8．理解费马小定理（当m是素数时，a m-1≡1(mod m)）和欧拉定理（aφ(m)≡1(mod m),其中φ(m)是1，2，…，m-1中与m互素的数的个数）及其证明。 9．了解数论在密码中的应用——公开密钥。 二、内容安排 本专题共安排了四讲，其中最后一讲“数论在密码中的应用”可根据教学时间的实际情况机动安排，可由教师讲授，也可作为学生课后的阅读材料。本专题教学时间约需18课时，具体分配如下（仅供参考）： 第一讲整数的整除约5课时 一、整除的概念和性质约2课时 二、最大公因数与最小公倍数约2课时
三集合非规范型容斥原理 ———————————————海南华图数资老师，胡军亮近些年考试经常出现容斥原理的题型，容斥原理分为两集合型跟三集合型，三集合容斥原理又包括规范型和非规范型，三集合容斥原理与三集合规范型容斥原理都是相对好掌握的。这里给大家讲解三集合非规范型容斥原理题的解题方法。首先看下面三个公式 （1） （2） （3） 公式（1）是规范型公式，公式（2）、（3）都是非规范型公式。 【例1】某乡镇对集贸市场36种食品进行检查，发现超过保质期的7种，防腐添加剂不合格的9种，产品外包装标识不规范的6种。其中，两项同时不合格的5种，三项同时不合格的2种。问三项全部合格的食品有多少种?（） A. 14 B. 21 C. 23 D. 32 解读：该题目为典型的容斥原理题，但是题目提到“两项同时不合格的有5种”，这句话的意思就是只满足两个条件的数量是5，该题属于三集合容斥原理非规范型题，带入公式（2）得到： 7+9+6-5-2*2=36-X，尾数法知道答案选C。 【例2】某市对52种建筑防水卷材产品进行质量抽检，其中有8种产品的低温柔度不合格，10种产品的可溶物含量不达标，9种产品的接缝剪切性能不合格，同时两项不合格的有7种，有1种产品这三项都不合格。则只有一项不合格的建筑防水卷材产品有多少种？ A. 17 B. 12 C. 15 D. 20 解读：该题涉及到只满足一项不合格、同时两项不合格、三项都不合格，属于三个集合非规范型容斥原理的题，带入公式（3）得到： 8+10+9=X+2*7+1，尾数法知道答案选B。 从上面的两道例题的讲解可以看到三集合非规范型容斥原理虽然不是很好理解，但是记住题型的特征，用正确的公式直接套用来解题还是很容易掌握的。 1 / 1
容斥原理问题——基础学习 一、解答题
2、两个集合容斥原理例1：四年级一班有54人，定阅《小学生优秀作文》和《数学大世界》两种读物的有13人，订阅《小学生优秀作文》的有45人每人至少订阅一种读物，订阅《数学大世界》的有多少人？（） A．13 B．22 C．33 D．41 【答案】B 【解题关键点】设A={定阅《小学生优秀作文》的人}，B={订阅《数学大世界》的人}，那么A∩B={同时订阅两本读物的人}，A∪B={至少订阅一样的人}，由容斥原则，B= A∪B+A∩B-A=54+13-45=22人。 【结束】 3、两个集合容斥原理例2：五年级有122名同学参加语文、数学考试，每个至少有一门功课取得优秀成绩，其中语文成绩优秀的有65人，数学成绩优秀的有87人。语文、数学都优秀的有多少人？（） A． 30 B．35 C．57 D．65 【答案】A
【解题关键点】此题是典型的两个集合的容斥问题，因此，可以直接有两个集合的容斥原理得到，语文和数学都优秀的学生有65+87-122=30人。 【结束】 4、两个集合容斥原理例3：学校文艺组每人至少会演奏一种乐器，已知会拉手提琴的有24人，会弹电子琴的有17人，其中两样都会的有8人。这个文艺组共有多少人？（）A．25 B．32 C．33 D．41 【答案】C 【解题关键点】设A={会拉手提琴的}，B={会弹电子琴的}，因此A∪B ={文艺组的人}，A∩B={两样都会的}，由两个集合的容斥原理可得：A∪B=A+B- A∩B=24+17-8=33。 【结束】 5、两个集合容斥原理例4：某班有36个同学在一项测试中，答对第一题的有25人，答对第二题的人有23人，两题都答对的有15人，问多少个同学两道题都没有答对？（）A．1 B．2 C．3 D．4 【答案】C 【解题关键点】有两个集合的容斥原理得到，至少答对一道题的同学有25+23-15=33人，因此两道题都没有答对的同学有36-33=3人。 【结束】
1.现有50名学生都做物理、化学实验，如果物理实验做正确的有40人，化学实验做正确的有31人，两种实验都错的有4人，则两种实验都做对的有( ) A、27人 B、25人 C、19人 D、10人 【答案】B 【解析】直接代入公式为：50=31+40+4－A∩B 得A∩B=25，所以答案为B。 2.某服装厂生产出来的一批衬衫大号和小号各占一半。其中25％是白色的，75％是蓝色的。如果这批衬衫共有100件，其中大号白色衬衫有10件，小号蓝色衬衫有多少件（） A、15 B、25 C、35 D、40 【答案】C 【解析】这是一种新题型，该种题型直接从求解出发，将所求答案设为A∩B，本题设小号和蓝色分别为两个事件A和B，小号占50%，蓝色占75%，直接代入公式为：100=50+75+10－A∩B，得：A∩B=35。 3.某高校对一些学生进行问卷调查。在接受调查的学生中，准备参加注册会计师考试的有63人，准备参加英语六级考试的有89人，准备参加计算机考试的有47人，三种考试都准备参加的有24人，准备只选择两种考试都参加的有46人，
不参加其中任何一种考试的都15人。问接受调查的学生共有多少人（）A．120 B．144 C．177 D．192 【答案】A 【解析】本题画图按中路突破原则，先填充三集合公共部分数字24，再推其他部分数字： 根据每个区域含义应用公式得到： 总数=各集合数之和－两两集合数之和＋三集合公共数＋三集合之外数 ＝63+89+47－{(x+24)+(z+24)+(y+24)}+24+15 ＝199－{（x+z+y）+24+24+24}+24+15 根据上述含义分析得到：x+z+y只属于两集合数之和，也就是该题所讲的只选择两种考试都参加的人数，所以x+z+y的值为46人；得本题答案为120. 4.对某单位的100名员工进行调查，结果发现他们喜欢看球赛和电影、戏剧。其中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，则只喜欢看电影的有多少人（） 人人人人 【答案】A 【解析】本题画图按中路突破原则，先填充三集合公共部分数字12，再推其他部分数字： 根据各区域含义及应用公式得到： 总数=各集合数之和－两两集合数之和＋三集合公共数＋三集合之外数 100＝58+38+52－{18+16+（12+ x）}+12+0,因为该题中，没有三种都不喜欢的人，所以三集合之外数为0，解方程得到：x＝14。52＝x+12+4+Y＝14+12+4+Y，得到Y＝22人。
2002 题二最大公约数与最小公倍数问题（20分） [问题描述] 输入二个正整数x0,y0（2≤x0<100000,2≤y0≤1000000）,求出满足下列条件的P，Q的个数： 条件：1. P,Q是正整数 2. 要求P,Q以x0为最大公约数，以y0为最小公倍数。 试求：满足条件的所有可能的两个正整数的个数。 [样例] 输入：x0=3 y0=60 输出：4 说明：（不用输出）此时的 P Q 分别为： 3 60 15 12 12 15 60 3 所以：满足条件的所有可能的两个正整数的个数共4种。 2012 1.质因数分解 (prime.cpp/c/pas) 【问题描述】 已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。 【输入】 输入文件名为prime.in。 输入只有一行，包含一个正整数n。 【输出】 输出文件名为prime.out。 输出只有一行，包含一个正整数p，即较大的那个质数。 【输入输出样例】 prime.in prime.out 21 7 【数据范围】 对于60%的数据，6 ≤ n ≤ 1000。 对于100%的数据，6 ≤ n ≤ 2*109。
2007年 4.Hanoi双塔问题 hanoi.pas/c/cpp 【问题描述】 给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将这些国盘移到C柱上，在移动过程中可放在B柱上暂存。要求: (1)每次只能移动一个圆盘； (2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序； 任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。 【输入】 输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。 【输出】 输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。 【限制】 对于50%的数据， 1<=n<=25 对于100% 数据， 1<=n<=200 【提示】 设法建立An与An-1的递推关系式。
1. 了解容斥原理二量重叠和三量重叠的内容； 2. 掌握容斥原理的在组合计数等各个方面的应用． 一、两量重叠问题 在一些计数问题中，经常遇到有关集合元素个数的计算．求两个集合并集的元素的个数，不能简单地把两个集合的元素个数相加，而要从两个集合个数之和中减去重复计算的元素个数，即减去交集的元素个数，用式子可表示成：A B A B A B =+-(其中符号“”读作“并”，相当于中文“和”或者“或”的意思；符号“”读作“交”，相当于中文“且”的意思．)则称这一公式为包含与排除原理，简称容斥原理．图示如下:A 表示小圆部分，B 表示大圆部分，C 表示大圆与小圆的公共部分，记为：A B ，即阴影面积．图示如下:A 表示小圆部分，B 表示大圆部分， C 表示大圆与小圆的公共部分，记为：A B ，即阴影面积． 包含与排除原理告诉我们，要计算两个集合A B 、的并集A B 的元素的个数，可分以下两步进行： 第一步：分别计算集合A B 、的元素个数，然后加起来，即先求A B +(意思是把A B 、的一切元素都“包含”进来，加在一起)； 第二步：从上面的和中减去交集的元素个数，即减去C A B =(意思是“排除”了重复计算的元素个数)． 二、三量重叠问题 A 类、 B 类与 C 类元素个数的总和A =类元素的个数B +类元素个数C +类元素个数-既是A 类又是B 类的元素个数-既是B 类又是C 类的元素个数-既是A 类又是C 类的元素个数+同时是A 类、B 类、C 类的元素个数．用符号表示为：A B C A B C A B B C A C A B C =++---+．图示如下： 教学目标 知识要点 7-7-5.容斥原理之最值问题 1．先包含——A B + 重叠部分A B 计算了2次，多加了1次； A B A B +-1 A B
课程简介：全国高中数学联赛是中国高中数学学科的最高等级的数学竞赛，其地位远高于各省自行组织的数学竞赛。在这项竞赛中取得优异成绩的全国约90名学生有资格参加由中国数学会主办的“中国数学奥林匹克（CMO）暨全国中学生数学冬令营”。优胜者可以自动获得各重点大学的保送资格。各省赛区一等奖前6名可参加中国数学奥林匹克，获得进入国家集训队的机会。中小学教育网重磅推出“全国高中数学联赛”辅导课程，无论是有意向参加竞赛的初学者，还是已入围二试的竞赛选手，都有适合的课程提供。本套课程由中国数学奥林匹克高级教练熊斌、人大附中数学教师李秋生等名师主讲，轻松突破你的数学极限！ 课程招生简章：https://www.doczj.com/doc/415071423.html,/webhtml/project/liansaigz.shtml 选课中心地址： https://www.doczj.com/doc/415071423.html,/selectcourse/commonCourse.shtm?courseeduid=170037#_170037_ 第一章数论专题 我们把未知数的个数多于方程的个数,且其解受到某种限制的方程,叫做不定方程.通常主要研究不定方程的正整数解、整数解、有理数解等. 不定方程问题的常见类型是： （1）求不定方程的解； （2）判定不定方程是否有解； （3）确定不定方程解的数量（有限还是无限）. 不定方程问题的常用解法是： （1）代数分析与恒等变形法，如因式分解、配方、换元等； （2）估计范围法，利用不等式放缩等方法,确定出方程中某些变量的取值范围,进而求整解； （3）同余法，即恰当选取模m,对方程两边做同余分析,以缩小变量的范围或发现性质,从而得出整解或判定无解； （4）构造法，构造出符合要求的特解,或构造一个求解的递推式,证明方程有无穷多解； （5）无穷递降法，无穷递降法是一种用反证法表现的特殊形式的归纳法,由Fermat创立并运用它证明了方程x4+y4=z4没有非零整解.从此,无穷递降作为一种重要的数学思想方法广为流传应用,并在平面几何、图论及组合中经常用到它. 引例：求所有正整数对（x,y）满足x y=y x-y.
容斥原理公式及运用 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，研究出一种新的计数方法。这种方法的基本思路是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。 一、容斥原理1：两个集合的容斥原理 如果被计数的事物有A、B两类，那么，先把A、B两个集合的元素个数相加，发现既是A类又是B类的部分重复计算了一次，所以要减去。如下图所示。 【示例1】??一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？ 数学得满分人数→A，语文得满分人数→B，数学、语文都是满分人数→A∩B，至少有一门得满分人数→A∪B。A∪B=15+12-4=23，共有23人至少有一门得满分。 二、容斥原理2：三个集合的容斥原理 如果被计数的事物有A、B、C三类，那么，将A、B、C三个集合的元素个数相加后发现两两重叠的部分重复计算了1次，三个集合公共部分被重复计算了2次。 如下图所示，灰色部分A∩B-A∩B∩C、B∩C-A∩B∩C、C∩A-A∩B∩C都被重复计算了1次，黑色部分A∩B∩C被重复计算了2次，因此总数A∪B∪C=A+B+C-（A∩B-A∩B∩C）-（B∩C-A∩B∩C）-（C∩A-A∩B∩C）-2A∩B∩C=A+B+C-A∩B-B∩C-C∩A+A∩B∩C。即得到： 【示例2】??某班有学生45人，每人都参加体育训练队，其中参加足球队的有25人，参加排球队的有22人，参加游泳队的有24人，足球、排球都参加的有12人，足球、游泳都参加的有9人，排球、游泳都参加的有8人，问：三项都参加的有多少人？ 参加足球队→A，参加排球队→B，参加游泳队→C，足球、排球都参加的→A∩B，足球、游泳都参加的→C∩A，排球、游泳都参加的→B∩C，三项都参加的→A∩B∩C。三项都参加的有A∩B∩C=A∪B∪C-A-B-C+A∩B+B∩C+C∩A=45-25-22-24+12+9+8=3人。
7-7-5.容斥原理之最值问题 教学目标 1.了解容斥原理二量重叠和三量重叠的内容； 2.掌握容斥原理的在组合计数等各个方面的应用． 知识要点 一、两量重叠问题 在一些计数问题中，经常遇到有关集合元素个数的计算．求两个集合并集的元素的个数，不能简单地把两个集合的元素个数相加，而要从两个集合个数之和中减去重复计算的元素个数，即减去交集的元素个数，用式子可表示成：A U B=A+B-A I B(其中符号“U”读作“并”，相当于中文“和”或者“或”的意思；符号“I”读作“交”，相当于中文“且”的意思．)则称这一公式为包含与排除原理，简称容斥原理．图示如下:A表示小圆部分，B表示大圆部分，C表示大圆与小圆的公共部分，记为：A I B，即阴影面积．图示如下:A表示小圆部分，B表示大圆部分，C表示大圆与小圆的公共部分，记为：A I B，即阴影面积． 1．先包含——A+B 重叠部分A I B计算了2次，多加了1次； 包含与排除原理告诉我们，要计算两个集合A、B的并集A U B的元素的个数，可分以下两步进行： 第一步：分别计算集合A、B的元素个数，然后加起来，即先求A+B(意思是把A、B的一切元素都“包含” 进来，加在一起)； 第二步：从上面的和中减去交集的元素个数，即减去C=A I B(意思是“排除”了重复计算的元素个数)．二、三量重叠问题 A类、B类与C类元素个数的总和=A类元素的个数+B类元素个数+C类元素个数-既是A类又是B类的元素个数-既是B类又是C类的元素个数-既是A类又是C类的元素个数+同时是A类、B类、C类的元素个数．用符号表示为：A U B U C=A+B+C-A I B-B I C-A I C+A I B I C．图示如下：
公务员考试行测备考：巧解三集合容斥原理问题 三集合容斥原理此类题型主要出现在近年来各省的省考中，主要是有三个独立的个体，此类题型主要的做题方法是公式法和作图法。近年来直接套用三集合公式的题目有所减少，开始出现条件变形的题目，不管容斥原理的题目怎么变化，但我们只要掌握住核心思想--剔除重复，那么做任何一个容斥原理题目都能够得心应手。 根据上图，可得三集合容斥原理核心公式： 一、直接利用公式型 【例1】（2012年4月联考）某公司招聘员工，按规定每人至多可投考两个职位，结果共42人报名，甲、乙、丙三个职位报名人数分别是22人、16人、25人，其中同时报甲、乙职位的人数为8人，同时报甲、丙职位的人数为6人，那么同时报乙、丙职位的人数为： A. 7人 B. 8人 C. 5人 D. 6人 【答案】A 【解析】设同时报乙、丙职位的人数为x，则根据三集合容斥原理公式有： 22+16+25-8-6-x+0=42-0，解得x=7。因此，本题答案为A选项。 二、三集合容斥原理作图型 国家公务员| 事业单位| 村官| 选调生| 教师招聘| 银行招聘| 信用社| 乡镇公务员| 各省公务员|
若在题目中任何一个位置看到“只满足”或“仅满足”，则公式法不能够再用，采用作图法来解题，注意，在作图的时候不管三七二十一，先画三个两两相交的圈，再往里填数字即可，填的时候注意从中间往外一层一层填。 【例2】（2007年江苏）一次运动会上，17名游泳运动员中，有8名参加了仰泳，有10名参加蛙泳，有12名参加了自由泳，有4名既参加仰泳又参加蛙泳，有6名既参加蛙泳又参加自由泳，有5名既参加仰泳又参加自由泳，有2名这3个项目都参加，这17名游泳运动员中，只参加1个项目的人有多少？（） A.5名 B.6名 C.7名 D.4名 【答案】B 【解析】本题问题中出现了“只”，故只能采用作图法。于是有 仰 只参加1个项目的人数为1+2+3=6。因此，本题答案为B选项。 国家公务员| 事业单位| 村官| 选调生| 教师招聘| 银行招聘| 信用社| 乡镇公务员| 各省公务员|
行测数学运算技巧：三集合整体重复型公式巧解容斥原理问题 一、介绍三集合整体重复型核心公式 在三集合题型中，假设满足三个条件的元素数量分别是A、B和C，而至少满足三个条件之一的元素的总量为W。其中，满足一个条件的元素数量为x，满足两个条件的元素数量为y，满足三个条件的元素数量为z，可以得到以下两个等式： W=x+y+z A+B+C=x×1+y×2+z×3 二、典型的三集合整体重复型的题目讲解 例1、某班有35个学生，每个学生至少参加英语小组、语文小组、数学小组中的一个课外活动。现已知参加英语小组的有17人，参加语文小组的有30人，参加数学小组的有13人。如果有5个学生三个小组全参加了，问有多少个学生只参加了一个小组?(2004年浙江公务员考试行测第20题) A. 15人 B.16人 C.17人 D.18人 【答案】A 解析：此题有两种解法可以解出： 解一：分别设只参加英语和语文、英语和数学、语文和数学小组的人为x、y、z，则只参加英语小组的人为17-5-x-y，只参加语文小组的人有30-5-x-z，只参加数学小组的人有13-5-y-z，则只参加三个小组中的一个小组的人和只参加其中两个小组的人和三个小组都参加的人的总和为总人数，即17-5-x-y+30-5-x-z+13-5-y-z+x+y+z+5=35。则求x+y+z=15，所以只参加一个小组的人数的和为15。 解二：套用三集合整体重复型公式： W=x+y+z A+B+C=x×1+y×2+z×3 35=x+y+5 17+30+13=x×1+y×2+5×3 解得：x= 15，y=15
例2、某调查公司就甲、乙、丙三部电影的收看情况向125人进行调查，有89人看过甲片，有47人看过乙片，有63人看过丙片，其中有24人三部电影全看过，20人一部也没有看过，则只看过其中两部电影的人数是( )(2009年江苏公务员考试行测A类试卷第19题) A. 69 B.65 C.57 D.46 【答案】D 解析：本题也是一道典型的三集合整体重复型题目，直接套用三集合整体重复型公式： W=x+y+z A+B+C=x×1+y×2+z×3 这里需要注意的是W=105，而非125， 105=x+y+24 89+47+63=x×1+y×2+24×3 两个方程，两个未知数，解出y=46，这里y表示只看过两部电影的人数，即所求。 例3、某高校对一些学生进行问卷调查。在接受调查的学生中，准备参加注册会计师考试的有63人，准备参加英语六级考试的有89人，准备参加计算机考试的有47人，三种考试?准备参加的有24人，准备选择两种考试参加的有46人，不参加其中任何一种考试的有15人。问接受调查的学生共有多少人?(2010年国家公务员考试行测第47题) A. 120 B.144 C.177 D.192 【答案】A 解析：本题的特征也很明显，直接套用公式，只是要注意的是，题目中最后问的是接受调查的总人数，我们求出W之后，还需要再加上不参加其中任何一种考试的那15个人， W=x+46+24 63+89+47=x×1+46×2+24×3 通过解方程，可以求出W=105，这只是至少准备参加一种考试的人数，所以接受调查的总人数为105+15=120。 例4、某市对52种建筑防水卷材产品进行质量抽检，其中有8种产品的低温柔度不合格，10种产品的可溶物含量不达标，9种产品的接缝剪切性能不合格，同时两项不合格的有7种，有1种产品这三项都不合格，则三项全部合格的建筑防水卷材产品有多少种?(2011 年国家公务员考试行测试卷第74题) A. 37 B.36 C.35 D.34