我们有时候在解题的时候，将问题分成几个子问题，然后叠加，但是答案中有重复解，也就是这些子问题相互具有重叠的部分，如果不分成子问题那么无疑会使解题过程变得更加麻烦。这时候容斥原理可以帮助解决这一难题。容斥原理就是先将子集问题的解相加，然后减去重复的解，再加上减的过程中重复减的部分，依次递推。
1.何谓容斥原理
在计数时，必须注意没有重复，没有遗漏。为了使重叠
部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
如果被计数的事物有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）。因为当A+B+C之后，相当于把A和B的公共部分加了两次，所以需要减去，同理也将B和C的公共部分加了两次，A和C的公共部分加了两次，所以需要减去。但是在减的过程中多减了ABC的公共部分，所以需要加上，从而得到最终解。
根据以上推理，将公式推导到一般化，公式如下：
2.例题讲解
2、3、5、7的倍数
题目大致意思是求求1-N中有多少个不是2或3或5或7的倍数。我们可以先解其反命题，即有多少个是2或3或5或7的倍数，最后用N相减即可。
根据容斥原理：首先，我们先将问题转化为四个子命题，即2的倍数、3的倍数、5的倍数和7的倍数四个子命题，各自的结果就是N/2、N/3、N/5、N/7。但是2的倍数和3的倍数这两个解有重复的部分，那就是减去其两者相乘得到的数的倍数即可，同理其它任意两个数同理；然后加上任意三个乘积的倍数；接着减去四个数乘积的倍数即可。最后再用N减去前面求到的结果。
代码如下：
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int total=(n/2+n/3+n/5+n/7)-(n/6+n/10+n/14+n/15+n/21+n/35)+(n/30+n/42+n/70+n/105)-n/210; int ans=n-total; System.out.println(ans); } } 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/228956.html原文链接：https://javaforall.net
