容斥定理+鸽巢原理 容斥定理
要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。
容斥原理：在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
公式表述公式的解释：
目的是求解m个集合的并集，首先将m个集合相加，减去集合间两两相交的部分，加上三三相交的部分，再减去四四相交的部分……一直到m个集合相交的部分，当m为偶数时，最后一项的符号为负数，否则为正数。
简单的说就是选中的是奇数个集合就相加，选中的是偶数个集合就相减，
在这里我们介绍一种方法那就是二进制枚举法；
我们先来思考一下这个问题：如果要对n个物体进行选择，那么有多少种情况？
这个我们应该怎么做呢？每个问题只有两种情况，那就是选与不选，这就相当于十几个集合求并集，如果选的是奇数个物品那么我们应该去加的，如果选的是偶数的物品，那么我们应该是相减的，但是我们应该怎么选呢？我们要实现的目的就是每次选的时候我们呢要知道哦我们选了多少个。而且我们还要知道我们选看谁，那么该怎么办呢？这就用到二进制枚举法了，既然这个方法的名字和二进制有关那么我们肯定也要用到二进制了是吧；
假如我们有三件物品，我们会有8种选择方案，我们先把他们一一的列举出来2，看看有什么规矩没；
他们所对应的十进制数
0 0 0 0
0 0 1 1
0 1 0 2
0 1 1 3
1 0 0 4
1 0 1 5
1 1 0 6
1 1 1 7
是不是一共这8种情况，看一下这些像不像是二进制呢？那么我们先把他们看一下他们对应的十进制数，把二进制写出来之后，大家有没有发现什么规矩呢？好像这些数字就是从0到2的n次方－1是吧。那么我们我们把这些数字遍历一下是不是就把所有可以选的情况全部遍历了呢？然后我们再用一个位运算，例如6对应的是1 0 1，我们可以分别取 1,0,1那么我们就知道了我们一共选择了两个物品，选择的物品分别是第一个物品和第三个物品。
代码实现：
#include<bits/stdc++.h>using namespace std;int main(){ int n;//一共n个物品； scanf("%d",&n); for(int i=0;i<(1<<n);i++)//从0到2的n次方-1； { for(int j=0;j<n;j++) //判断第j个物品有没有被选中； printf("%d ",1&(i>>j)); printf("n"); } return 0;}/*运行结果30 0 01 0 00 1 01 1 00 0 11 0 10 1 11 1 1*/ 例题：C；题意：
这个题的大致意思就是说给你一个区间a到b，再给你一个数字n，找一下在所给的区间中和n互质的个数，
这个题我们应该怎么做呢？首先我们应该先把n用质因子分解法把n分解成几个质数，然后再找出和n的质因子不互质，也就是是n的质因子的倍数的个数，至于区间不是从1开始的这个问题也很好解决，我们只需要看成两个区间最后再一减就行了；
第一步：求出n的质因子：2,3,5；
第二步：(1,m)中是n的因子的倍数当然就不互质了(2,4,6,8,10)->n/2 6个,(3,6,9,12)->n/3 4个,(5,10)->n/5 2个。
如果是粗心的同学就把它们全部加起来就是：6+4+2=12个了，那你就大错特错了,里面明显出现了重复的,我们现在要处理的就是如何去掉那些重复的了！
第三步：这里就需要用到容斥原理了，公式就是：n/2+n/3+n/5-n/(2*3)-n/(2*5)-n/(3*5)+n/(2*3*5).
第四步:我们该如何实现呢？就用我刚才讲的二进制枚举。
代码：
#include<bits/stdc++.h>using namespace std;#define ll long long#define met(Q,QQ) memset(Q,QQ,sizeof(Q))int main(){ ll t,A,B,n,a[103]; scanf("%lld",&t); ll aaa=0; while(t--) { aaa++; met(a,0); scanf("%lld %lld %lld",&A,&B,&n); ll cnt=0; for(int i=2;i*i<=n;i++) //质因子分解 { if(n%i==0) { cnt++; a[cnt]=i; } while(n%i==0) { n/=i; } } if(n!=1) { cnt++; a[cnt]=n; } ll SUM=0; for(int i=1;i<(1<<cnt);i++)//二进制枚举 { ll sum=1,cnt1=0; for(int j=0;j<cnt;j++) { if(1&(i>>j)) //判断有没有选中这个集合, { sum*=a[j+1]; //选中的数字的乘积 cnt1++;; //选中的个数 } } if(cnt1&1) { SUM+=B/sum; SUM-=(A-1)/sum; } else { SUM-=B/sum; SUM+=(A-1)/sum; } } printf("Case #%lld: %lldn",aaa,B-A+1-SUM); } return 0;} 鸽巢原理： 基本描述桌子上有是个苹果，把这十个苹果放到九个抽屉里，无论怎么放，我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是所说的“抽屉原理”。
更一般的表述：如果每一个抽屉代表一个集合，每一个苹果就可以代表一个元素。加入有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。
原理1
把多余n+1个物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。
原理2
把多余mn+1(n不为0)个物体放到n个抽屉里面，则至少有一个抽屉里面不少于(m+1)的物体。
第二抽屉原理把(mn -1 )个物体放入n个抽屉中，其中必须有一个抽屉不多余(m-1)个物体。
如将3*5-1 = 14个物体放入5个抽屉中，则必定有一个抽屉中的物体数目少于3-1=2.
属相问题
属相有12个，那么任意37个人中，至少有几个人属相相同？
上取整(37 / 12) = 4
招聘问题
有300人到招聘会求职，其中软件设计有100人，市场营销有80人，财务管理有70人，人力资源管理有50人。那么至少有多少人找到工作才能保证一定有70人找的工作专业相同？
考虑最差情况，即软件设计，市场营销，财务管理均招了69人，人力资源管理招了50人，此时再多招1人，就有70人找的工作专业相同了。
故答案为 69*3 + 50 + 1 = 258
衬衫问题
一个抽屉里有20件衬衫，其中4件是蓝的，7件是灰的，9件是红的，则应从中随意取出多少件才能保证有5件是同颜色的？
考虑最差情况，即已经取出了4件蓝色，4件灰色，4件红色，再多取出1件就满足条件。
故答案为 4 + 4 + 4 + 1 = 13
例题 D
题目大意就是先给出一个数N，接着再给出N个数，要你从这N个数中任意选择1个或多个数，使得其和是N的倍数
如果找不到这样的答案 则输出0
答案可能有多个，但智勇任意输出一个解就行。
输出的第一行是选择元素的个数M，接着M行分别是选择的元素的值
jydby并不同为什么这一题回事抽屉原理，分析后才明白，昨晚后更有体会
实际上此题一定有解，不存在输出0的结果
证明如下
我们可以依次求出a[0],a[0]+a[1],a[0]+a[1]+a[2],......,a[0]+a[1]+a[2]...+a[n]；
假设分别是sum[0],sum[1],sum[2],......,sum[n]
如果在某一项存在是N的倍数，则很好解，即可直接从第一项开始直接输出答案
但如果不存在，则sum[i]%N的值必定在[1,N-1]之间，又由于有n项sum，有抽屉原理：
把多于n个的物体放到n个抽屉里，则至少有一个抽屉里有2个或2个以上的物体。则必定有一对i，j，使得sum[i]=sum[j]，其中i！=j，不妨设j>i
则（sum[j]-sum[i]）%N=0，故sum[j]-sum[i]是N的倍数
则只要输出从i+1～j的所有的a的值就是答案
代码：
#include<stdio.h>#include<string.h>using namespace std;#define met(Q,QQ) memset(Q,QQ,sizeof(QQ))const int maxn=1e4+5;int sum[maxn],a[maxn];//取模后的前缀和int b[maxn];//标记作用，判断这个前缀和前面有没有出现过,int main(){ int n; met(sum,0); met(b,0); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]=(sum[i-1]+a[i])%n; } for(int i=1;i<=n;i++) { if(sum[i]==0) { printf("%dn",i); for(int j=1;j<=i;j++) { if(j!=1) printf(" %d",a[j]); else printf("%d",a[j]); } break; } if(b[sum[i]]==0) { b[sum[i]]=i; } else { printf("%dn",i-b[sum[i]]); for(int j=b[sum[i]]+1;j<=i;j++) { if(j!=b[sum[i]]+1) printf(" %d",a[j]); else printf("%d",a[j]); } break; } } return 0;}