【数论】组合数学—容斥原理
概念
在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
２.举例
（１）如果被计数的事物有A，B两类，那么，A类和B类元素个数总和=A类元素个数+B类元素个数-即使A类又是B类元素个数。
那么公式就是：
|A∪B| = |A| + |B| - |A∩B|
可以用下面的图表示（也叫韦恩图）：
U表示全集（整个集合），A表示符合A类的数量，B表示符合B类的数量，I表示既不符合A也不符合B的数量，AB表示既符合A也符合B的数量，则U-I=A+B-AB。
（2）如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数-既是A类又是B类的元素个数-既是A类又是C类的元素个数-既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。
|A∪B∪C| = |A| + |B| + |C| - |A∩B| - |B∩C| - | C∩A | + |A∩B∩C|
可以用下面的图表示：
U表示整个大集合，A表示符合A类的数量，B表示符合B类的数量，C表示符合C类的数量，I表示既不符合A也不符合B还不符合C的数量，AB表示既符合A也符合B的数量，BC表是同时符合B和C的数量，AC表示既符合A也符合C的数量，ABC表示同时符合A、B、C的数量。
根据容斥原理的定义，先不考虑重叠，把某内容的所有对象数目先计算出来（即A+B+C）；再剔除重复计算的数目，AB这部分被计算了两次，也就是重复了一次，要剪掉，同理BC，AC也要个减掉一次；
那ABC呢？在A+B+C中我们把ABC统计了三次，所以理论上需要减掉两次，但是ABC同时又在AB、AC、BC中，也就是说我们减去AB的时候已经减了一次ABC，减去BC的时候又减了一次ABC，减AC的时候再一次减掉了ABC，即ABC总共减了三次。所以就需要额外再加回来一次。
那么等量关系就变成了U-I=A+B+C-AB-AC-BC+ABC
3.例题
（1）为了发展体育运动，学校这学期开了体育兴趣课，学生需要从篮球和足球中选，允许两个同时选或同时不选。一个班级有50人，选了篮球的有32人，选了足球的有21人，两种都选了的有17人。问：有多少同学两种都没选。
如上图所示，篮球32人和足球21人，用总数50减去篮球再减去足球，中间重叠的部分被减了两次，所以再加一个中间重叠部分。50-32-21+17=14人。
（2）某校六⑴班有学生55人，每人在暑假里都参加体育训练队，其中参加足球队的有22人，参加排球队的有23人，参加游泳队的有24人，足球、排球都参加的有11人，足球、游泳都参加的有10人，排球、游泳都参加的有9人，问：三项都参加的有多少人？
我们假设足球队是A，排球队是B，游泳队是C。那么根据公式 |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |B∩C| - | C∩A | + |A∩B∩C| 可以得出。
55 = 22+23+24-11-10-9 + |A∩B∩C| 。该式子计算得：16
（3） 假设班里有50名学生，每个人都必须选修一门运动科目，选修篮球的有15人，选修足球的有20人，选修乒乓球的有30人，同时选修篮球和足球的有10人，同时选修乒乓球和足球的有18人，同时选修篮球和乒乓球的有12人，问选修了三门科目的有多少人？
根据上面的公式，可以15+20+30-10-18-12 + x =50。得x=25。
思考一下？
4.常见题目类型：
（1）排列问题：
由0到9的数字组成排列，要求第一个数大于1，最后一个数小于8，一共有多少种排列？
（2）序列问题：
长度为n的由数字0，1，2组成的序列，要求每个数字至少出现1次，这样的序列有多少种？
（3）方程组整数解问题
给出一个方程：x1+x2+x3+x4+x5+x6=20, 对于每个 0<=xi<=8，求解这个方程组有多少组解。
（3）区间内互素个数
给出整数n和r。求区间[1;r]中与n互素的数的个数。
(4)至少一个被整除问题
(5)匹配字符串个数问题
给出n个匹配串，它们长度相同，其中有一些’?’表示待匹配的字母。然后给出一个整数k，求能正好匹配k个匹配串的字符串的个数。更进一步，求至少匹配k个匹配串的字符串的个数。
(6)路径数据问题
在一个的n*m方格阵中，有k个格子是不可穿越的墙。一开始在格子(1,1)（最左下角的格子）中有一个机器人。这个机器人只能向上或向右行进，最后它将到达位于格子(n,m)的笼子里，其间不能经过障碍物格子。求一共有多少种路线可以到达终点。
(7)数组四元组问题
5.应用
【题目描述】
求1到n范围内能被4，5，6整除的数的个数
【输入描述】
第一行t,表示有t组数据。
后面t行，每行一个n。（1<n<10^8）
【输出描述】
【样例输入】
10
【样例输出】
5
【题目分析】
注意题目求的是个数。
题目本身可以用暴力+模拟的方式求解，但是考虑数据量，可以接用容斥原理来进行求解。
能被4，5整除，就是4和5的最小公倍数20，（AB）
能被4，6整除，就是4和6的最小公倍数12，（AC）
能被5，6整除，就是5和6的最小公倍数30，（BC）
能被4，5，6整除，就是4，5，6的最小公倍数120（ABC）
总数sum= n/4 + n/5 + n/6 。
那么 两两之间的公倍数 n/20 + n/12 + n/30，应该减去。
那么 三个数的公倍数，n/120 应该加上。
【参考答案】
#include <iostream>
using namespace std;
int main() {
int x,y,sum;
int t,n;
cin>>t;
while(t--) {
cin>>n;
x = n/20+n/12+n/30; //两两之间的公倍数
y = n/60; //三个数的公倍数
sum = n/4+n/5+n/6;
cout<<sum-x+y<<endl;
}
return 0;
}上面的题目如果提高难度，改成”求1到n范围内能被a，b，c整除的数的个数“ 应该怎么做？
题目2：
【题目描述】
你是一个喜欢编程的手机经销商，一次你得到了一个边长为n的正方体箱子，里面装满了长，宽，高为a,b,c的手机盒，手机盒均朝同一方向摆放。这时，一束阳光正好照过正方体箱子的对角线，你想知道，这一束阳光穿过了多少手机盒。
(n<=100000,a,b,c均为n的约数)。
【输入描述】
输入4个正整数，分别表示n,a,b,c。
【输出描述】
【样例输入】
10 5 2 2
【样例输出】
6
【题目分析】
假设上面就是边长为n的正方体，这里面有装满了长宽高为a，b，c的手机盒。
从对角线穿过（左上到右下或者右上到左下），穿过长的条数为 n/a , 穿过宽的条数为 n/b ,但是会穿过顶点，而它又被加了两次，所以减去n/lcm( a , b)。
lcm是求最小公倍数：
long long gcd(long long x,long long y) {
if(!y)
return x;
else {
r=gcd(y,x%y);
return r;
}
}那么 总的是 n/a+n/b+n/c
两两：n/lcm(a,b)+n/lcm(b,c)+n/lcm(a,c)
三个：n/lcm(lcm(b,c),a))
#include<iostream>
using namespace std;
long long n,a,b,c;
long long gcd(long long x,long long y) {
if(!y)
return x;
else {
int r=gcd(y,x%y);
return r;
}
}
long long lcm(long long x,long long y) {
return x*y/gcd(x,y);
}
int main() {
cin>>n>>a>>b>>c;
long long A=n/a+n/b+n/c;
long long B=n/lcm(a,b)+n/lcm(b,c)+n/lcm(a,c);
long long C=n/lcm(lcm(b,c),a);
cout<<A-B+C<<endl;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
