容斥原理常见的问题如下。
(1) 篮球、羽毛球、网球三种运动，至少会一种的有22人，会篮球的有15人，会羽毛球的有17人，会网球的有12人，既会篮球又会羽毛球的有11人，既会羽毛球又会网球的有7人，既会篮球又会网球的有9人，那么三种运动都会的有多少人?
(2) 《西游记》《三国演义》《红楼梦》三大名著，至少读过其中一本的有20人，读过《西游记》的有10人，读过《三国演义》的有12人，读过《红楼梦》的有15人，读过《西游记》《三国演义》的有8人，读过《三国演义》《红楼梦》的有9人，读过《西游记》《红楼梦》的有7人。问三本书全都读过的有多少人?
01、原理概述
容斥原理是一种较常用的计数方法，其基本思想是: 先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏，又无重复。
容斥原理核心的计数规则可以记为一句话: 奇加偶减。
假设被计数的有A、B、C三类，那么，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，如图1所示。
■ 图1容斥定理
当被计数的种类被推到n类时，其统计规则遵循奇加偶减。
容斥定理最常用于求［a,b］区间与n互质的数的个数，该问题可视为求［1,b］区间与n互质的个数减去［1,a-1］区间内与n互质的个数，故可先对n进行因子分解，然后从［1,b］、［1,a-1］区间中减去存在n的因子的个数，再根据容斥定理，奇加偶减，对n的因子的最小公倍数的个数进行处理即可。
02、常见应用
- 求［a,b］中与n互素的个数
问题可转换为区间［1,b］中与n互素的数的个数减去区间［1,a-1］中与n互素的数的个数，那么问题就转换为对于n，求1～k中与n互质的数有多少个，因此可以先反着求1～k中与n不互质的数有多少个。
故对n进行因子分解，然后从1～k中减去不能与n整除的数的个数，然后根据容斥定理奇加偶减，最后答案是: 1～b的元素个数减去1～a-1的元素个数再减去1～b中与n不互质的数的个数加上1～a-1中与n互质的数的个数，即b-(a-1)-calculate(b)+calculate(a-1)
bool bprime[N];LI prime[N],cnt,factor[N],num;void isprime() l
//筛选素数
cnt=0;
memset(bprime,false,sizeof(bprime)) ;for(LL i=2; i<N; i+) {
if(!bprime[i]) [prime[cnt++]=i;for(LL j=i*i; j<N; j+=i)bprime[il=true;
void getFactor(int n){
num= 0;
for(LL i=0;prime[i] *prime[i]<=n&&i<cnt; i++) {
if(n%prime[il==0) [factor[num++]=prime[il;while(n%prime[il== 0)n/=prime[il;
//记录 n 的因子
if(n!=1)
//1 既不是素数，也不是合数
factor[num++]=n;
LI calculate(LL m,LL num) (
LL res=0;
for(LL i=l; i<(1<<num); i++) {
LL sum= 0;
LI temp=1;
for(LL j=0;j<num; j++) {
if(i&(1<<j)) {
sum+ + ;
temp *=factor[j];
if(sum%2)
res+=m/temp;
else
res-=m/temp;
return res;
int main() {
isprime();
LL a,b,n;
scanf("%1ld%lld号lld",&a,&b,&n);getFactor(n)//容斥定理，奇加偶减LL res= (b-(a-1)-calculate(b,num))+calculate(a-1,num);printf("lld\n",res);return 0;
- 求［1,n］中能/不能被m个数整除的个数
对于任意一个数a［i］来说，我们知道在1-n中有n/a［i］个数是a［i］的倍数，但这样将m个数扫一遍一定会用重复的数，因此需要用到容斥原理。
根据容斥定理的奇加偶减，对于m个数来说，其中的任意2，4，…，2k个数就要减去它们最小公倍数能组成的数，1，3，…，2k+1个数就要加上它们的最小公倍数，因此m个数就有2m种情况，对于每种状态，依次判断由多少种数组成，然后再进行奇加偶减即可。
根据容斥原理有: sum=从m中选1个数得到的倍数的个数-从m中选2个数得到的倍数的个数+从m中选3个数得到的倍数的个数-从m中选4个数得到的倍数的个数……
那么,能被整除的个数就是sum，不能被整除的个数就是n-sum。
LL GCD(IL a,LL b) {
return !b? a:GCD(b,ab) ;
LL LCM(LL a,LL b)[
return a/GCD(a,b) *b;
IL a[N];
int main(){
II n;
int m;
scanf("1ldd",&n, &m) ;for(int i=0;i<m;i++)scanf("%lld",&alil);
LL sum= 0;for(int i=0;i<(1<<m) ;i++){
LL lcm= 1;LL cnt=0;for(int j=0;j<m;j++){
if(i&(1<<j)){
lcm=LCM(lcm,aljl) ;cnt++;
//2”种状态
//从 m 中选出个数
if(cnt!=0){
if(cnt&1)
//奇加
sum+=n/lcm;
else
//偶减
sum-=n/1cm;
printf(%lld "lld\n",sum,n-sum);return 0;
