容斥原理

这个东西需要由数学中的集合引入

\(S_1=\{1,2,3,4\}\) \(S_2=\{2,4,5\}\)

求\(S_1\cup S_2\) 的大小

根据我们高中的知识很容易可以知道\(S_1\cup S_2\) 的大小是\(5\)

那究竟是怎么来的呢

我们可以推出这样一个式子：|\(S_1\cup S_2\)| = |\(S_1\)|+|\(S_2\)|-|\(S_1\cap S_2\)|

那如果是三个集合求交集呢

\(S_1=\{1,2,3,4\}\) \(S_2=\{2,4,5\}\) \(S_3=\{4,5,6\}\)

通过观察法我们很容易知道 |\(S_1\cup S_2\cup S_3\)| \(=\) \(6\)

那如果用式子推导呢

我们试着套用一下上面的式子

\(6=\)|\(S_1\cup S_2\cup S_3\)| \(\neq\) |\(S_1\)|+|\(S_2\)|+|\(S_3\)|-|\(S_1\cap S_2\)|-|\(S_1\cap S_3\)|-|\(S_2\cap S_3\)|\(=5\)

我们观察可以发现\(S_1\cap S_2\cap S_3\)这一部分是被加了三次被减了三次的

所以我们就需要将其加回来

最终的公式为

|\(S_1\cup S_2\cup S_3\)| = |\(S_1\)|+|\(S_2\)|+|\(S_3\)|-|\(S_1\cap S_2\)|-|\(S_1\cap S_3\)|-|\(S_2\cap S_3\)|+|\(S_1\cap S_2\cap S_3\)|

通过观察我们可以发现并集的大小是奇数个集合的交集减去偶数个集合的交集

通过推导我们发现后面的集合都符合这个规律

记\(S_i\)为\(1-n\) 中能整除\(p_i\)的集合,那么根据容斥原理, 所有数的个数为各个集合的并集，计算公式如下
\(⋃_{i=1}^{m}S_i=S_1+S_2+…+S_m−(S_1⋂S_2+S_1⋂S_3+…+S_{m−1}⋂S_m)+\)
\((S_1⋂S_2⋂S_3+…+S_{m−2}⋂S_{m−1}⋂S_m)+…+(−1)^{m−1}(⋂_{i=1}^{m}S)\)

以上就是容斥原理

习题：

890. 能被整除的数 - AcWing题库