什么是容斥原理

容斥原理是一种计数手段。例如在下图中，我们想不重复、不遗漏的求出包含在ABC三个集合中所包含的元素的个数，应该使用怎么样的方法呢？

这个问题对于我们来说并不陌生，当然也并不困难。直观的方法是把所有的元素计数，再把重复的元素排除出去。这种计数的方法，有“容”有“斥”，我们讲其称做“容斥原理”。

容斥原理的应用

小规模的计数问题自然难不倒我们，我们甚至可以使用visit[]数组来记录某元素是否出现。但是当问题的规模增大时，使用数组记录这种方式需要使用更多的内存，在很多情况下，这是我们不能接受的。

考虑一个问题

问题：统计在1~N中的，能被2或3整除的数。(1 <= N <= 1e9)

我们先把这个问题拆成两部分来看：

1. N以内的，能被2整除的数
2. N以内的，能被3整除的数

这两个问题都非常简单，我们可以直接使用除法进行求解，其结果分别为N/2和N/3。

与此同时 …

more ...