c+d为什么不能容斥

概念：

在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

好了，我们理解概念，开始例题吧。

例题一：

描述：

一年级某班有30人，考了语文和数学，语文上90的有17人，数学上90的有25人，语文和数学同时上90的有15人。问有多少同学两门课都没有上90？

答案：

3人。

分析：

如图，上了语文90分的人和上了语文90分的人的和重复了语文和数学同时上的人，所以是：30-17-25+15=3人。

例题二：

描述：

假设班里有50名学生，每个人都必须选修一门运动科目，选修篮球的有15人，选修足球的有20人，选修乒乓球的有30人，同时选修篮球和足球的有10人，同时选修乒乓球和足球的有18人，同时选修篮球和乒乓球的有12人，问选修了三门科目的有多少人？

答案：

无解。

分析：

WHAT？！！你的心里一定是这样想的。

别急我们分析一下：

选修篮球的加选修足球的加选修乒乓球的减去同时选修篮球和足球的和同时选修乒乓球和足球的与同时选修篮球和乒乓球的就是

班里人数减去三门都选修了的。

所以应是25人。

可是，选修篮球的就只有15人，那么多的10人从何而来呢？

所以无解。

例题三：

描述：

你是一个喜欢编程的手机经销商，一次你得到了一个边长为n的正方体箱子，里面装满了长，宽，高为a,b,c的华为手机盒，手机盒均朝同一方向摆放。这时，一束阳光正好照过正方体箱子的对角线，你想知道，这一束阳光穿过了多少手机盒。

(n<=100000,a,b,c均为n的约数)。

输入：

输入4个正整数，分别表示n,a,b,c。

输出：

输出光束穿过手机盒的数量。

输入样例：

10 5 2 2

登录后复制

输出样例：

6

登录后复制

思路分析：

我们先从二维平面开始讲，因为从对角线穿过，所以它只会穿过上底和右高（从左上到右下）。

那么穿过长的条数为n/a，宽的条数为n/b，但是会穿过顶点，而它又被加了两次，所以减去n/lcm( a , b)。

lcm指的是最小公倍数。

来到三维也是这个操作。

就是：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

#include

#include

long long n,a,b,c;

long long gcd(long long x,long long y)

{

if(!y)

return x;

else

{

r=gcd(y,x%y);

return r;

}

}

long long lcm(long long x,long long y)

{

return x*y/gcd(x,y);

}

int main()

{

scanf("%lld%lld%lld%lld",&n,&a,&b,&c);

printf("%lld",n/a+n/b+n/c-n/lcm(a,b)-n/lcm(b,c)-n/lcm(a,c)+n/lcm(lcm(b,c),a));

}

登录后复制

C++

容斥原理

二手天籁报价及

精选推荐

广告

容斥原理+拓展

6下载·0评论

2018年10月25日

容斥原理（模板+例题）

4365阅读·0评论·1点赞

2017年8月5日

P2567（容斥原理+递归写法（类似于背包的递归写法））

73阅读·0评论·0点赞

2020年7月5日

容斥原理dfs

339阅读·0评论·0点赞

2018年4月19日

HDU 4135 Co-prime

407阅读·0评论·0点赞

2015年4月28日

容斥原理——数学知识（c++）

394阅读·0评论·1点赞

2020年11月28日

这才是我想要的播放器，你用过了么？

精选推荐

广告

C++容斥原理—————表达式计数

1141阅读·0评论·1点赞

2019年3月25日

C/C++容斥定理

215阅读·0评论·0点赞

2020年4月1日

C++数论容斥原理—————无关的元素

237阅读·0评论·1点赞

2019年3月20日

容斥原理（三元容斥，四元容斥）

1655阅读·0评论·0点赞

2019年4月19日

容斥原理模板

2106阅读·0评论·0点赞

2015年5月7日

数学知识：容斥原理

872阅读·3评论·19点赞

2021年6月7日

#容斥，组合计数#洛谷 3214 卡农

152阅读·0评论·0点赞

2019年4月26日

容斥原理级笔记

356阅读·0评论·0点赞

2022年1月24日

专题总结容斥原理（持续更新）

5002阅读·0评论·7点赞

2016年7月10日

容斥定理（转载）

1122阅读·0评论·5点赞

2012年12月10日

Java & Pascal & C++——容斥原理例题——切蛋糕

1151阅读·0评论·0点赞

2017年7月7日

容斥原理

1388阅读·0评论·1点赞

2018年8月17日

去首页

看看更多热门内容