容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。
描述容斥原理可以描述如下：
要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。
对于实际问题的应用容斥原理的理论需要通过例子才能很好的理解。
首先，我们用三个简单的例子来阐释这个理论。然后会讨论一些复杂问题，试看如何用容斥原理来解决它们。
其中的“寻找路径数”是一个特殊的例子，它反映了容斥问题有时可以在多项式级复杂度内解决，不一定需要指数级。
一个简单的排列问题由0到9的数字组成排列，要求第一个数大于1，最后一个数小于8，一共有多少种排列？
我们可以来计算它的逆问题，即第一个元素<=1或者最后一个元素>=8的情况。
我们设第一个元素<=1时有X组排列，最后一个元素>=8时有Y组排列。那么通过容斥原理来解决就可以写成：
经过简单的组合运算，我们得到了结果：
然后被总的排列数10!减，就是最终的答案了。
（0,1,2）序列问题长度为n的由数字0，1，2组成的序列，要求每个数字至少出现1次，这样的序列有多少种？
同样的，我们转向它的逆问题。也就是不出现这些数字的序列 不出现其中某些数字的序列。
我们定义Ai(i=0…2)表示不出现数字i的序列数，那么由容斥原理，我们得到该逆问题的结果为：
可以发现每个Ai的值都为2^n（因为这些序列中只能包含两种数字）。而所有的两两组合都为1（它们只包含1种数字）。最后，三个集合的交集为0。（因为它不包含数字，所以不存在）
要记得我们解决的是它的逆问题，所以要用总数减掉，得到最终结果：
方程整数解问题
给出一个方程：
其中。
求这个方程的整数解有多少组。
我们先不去理会xi<=8的条件，来考虑所有正整数解的情况。这个很容易用组合数来求解，我们要把20个元素分成6组，也就是添加5块“夹板”，然后在25个位置中找5块“夹板”的位置。
然后通过容斥原理来讨论它的逆问题，也就是x>=9时的解。
我们定义Ak为xk>=9并且其他xi>=0时的集合，同样我们用上面的添加“夹板”法来计算Ak的大小，因为有9个位置已经被xk所利用了，所以：
然后计算两个这样的集合Ak、Ap的交集：
因为所有x的和不能超过20，所以三个或三个以上这样的集合时是不能同时出现的，它们的交集都为0。最后我们用总数剪掉用容斥原理所求逆问题的答案，就得到了最终结果：
求指定区间内与n互素的数的个数：
给出整数n和r。求区间[1;r]中与n互素的数的个数。
去解决它的逆问题，求不与n互素的数的个数。
考虑n的所有素因子pi(i=2…k)
在[1;r]中有多少数能被pi整除呢？它就是：
然而，如果我们单纯将所有结果相加，会得到错误答案。有些数可能被统计多次（被好几个素因子整除）。所以，我们要运用容斥原理来解决。
我们可以用2^k的算法求出所有的pi组合，然后计算每种组合的pi乘积，通过容斥原理来对结果进行加减处理。
如求[1,10]中与6互素的数有多少个：首先去解决它的逆问题，求不与n互素的数的个数。
6的素因子有2,3；那么sum=10/2+10/3-10/(2*3)=5+3-1=7；
所以[1,10]中与6互素的数有10-7=3（为5,7,9）；
sum=10/2+10/3-10/(2*3)=5+3-1=7；公式中的分子为{2,3}的非空子集，每个子集都可以用二进制表示：10（选了2没选3）,01（选了3没选2）,11（选了2选了3）
代码实现
二进制实现：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<vector> 7 #define ll long long 8 using namespace std; 9 vector<int>p;//存放质因数10 int prime[5000]11 int visit[5000];12 //用筛法初始化40000以内的质数，将质数存放在prime数组中，m记录大小13 void init()14 {15 k=0;16 memset(visit,0,sizeof(visit));17 for(int i=2;i<5000;i++)18 {19 if(!visit[i])prime[k++]=i;20 for(int j=0;j<k&&i*prime[j]<5000;j++)21 {22 visit[i*prime[j]]=1;23 if(i%prime[j]==0)break;24 }25 }26 }27 //对n分解质因数28 void factor(int n)29 {30 for(int i=0;i<k&&prime[i]*prime[i]<n;i++)31 {32 if(n%prime[i]==0)33 {34 p.push_back(prime[i]);35 while(n%prime[i]==0)36 {37 n/=prime[i];38 }39 }40 }41 if(n>1)p.push_back(n);42 }43 //用二进制实现容斥原理,求区间[1,r]内与n互素的数的个数44 int slove(int r)45 {46 int sum=0;47 for(i=1;i<1<<p.size();i++)48 {49 //i的范围是1-2^p.size()，空集除外，每一个子集所对应的50 //二进制都不一样，也就是i51 int mult=1,bit=0;52 for(j=0;j<p.size();j++)53 {54 if(i&1<<j)55 {//与i的二进制的第j位比较，看是否为1，是则选中56 bit++;//计算i中1的个数，也就是质因数的个数57 mult*=p[j];58 }59 }60 if(bit&1)//若1的个数是奇数则进行加法，否则进行减法61 sum+=r/mult;62 else63 sum-=r/mult;64 }65 return r-sum;//用总的数目-与n不互素的个数66 }67 int main()68 {69 int n,m;70 init();71 while(~scanf("%d%d",&n,&m))72 {73 factor(n);74 printf("%dn",slove(m));75 }76 return 0;77 }dfs实现：
hdu1796
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define ll long long 7 using namespace std; 8 int a[30],ans,k; 9 int n,m;10 int gcd(ll a,ll b)11 {12 return b==0?a:gcd(b,a%b);13 }14 void dfs(ll cur,ll lcm,int cnt)15 {16 lcm=a[cur]/gcd(a[cur],lcm)*lcm;//dfs遍历实现分子遍历17 if(cnt&1)18 ans+=(n-1)/lcm;19 else20 ans-=(n-1)/lcm;21 for(int i=cur+1;i<k;i++)22 dfs(i,lcm,cnt+1);23 }24 int main()25 {26 int i,j;27 while(~scanf("%d%d",&n,&m))28 {29 ans=0;k=0;30 for(i=0;i<m;i++)31 {32 scanf("%d",&j);33 if(j)a[k++]=j;34 }35 for(i=0;i<k;i++)36 dfs(i,a[i],1);37 printf("%dn",ans);38 }39 return 0;40 }队列数组实现：
hdu4135
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 __int64 fac[100000]; 8 __int64 k; 9 void init(__int64 n)10 {11 int i;k=0;12 for(i=2;i*i<n;i++)13 {14 if(n%i==0)15 {16 fac[k++]=i;17 while(n%i==0)18 {19 n/=i;20 }21 }22 23 }24 if(n>1)25 fac[k++]=n;26 }27 __int64 haha(__int64 n)28 {29 __int64 ha[10000],i,j,m,t=0,num=0;30 ha[t++]=-1;31 for(i=0;i<k;i++)32 {33 m=t;34 for(j=0;j<m;j++)35 ha[t++]=ha[j]*fac[i]*(-1);//队列数组实现分子遍历36 }37 for(i=1;i<t;i++)38 {39 num+=n/ha[i];40 printf("%I64d ",ha[i]);41 }42 return num;43 }44 int main()45 {46 int t,i;__int64 n,a,b;47 scanf("%d",&t);48 for(i=1;i<=t;i++)49 {50 scanf("%I64d%I64d%I64d",&a,&b,&n);51 memset(fac,0,sizeof(fac));52 init(n);53 printf("Case #%d: %I64dn",i,b-haha(b)-(a-1-haha(a-1)));54 }55 return 0;56 }