离散数学 - 容差原理

先来看一下对于容斥原理的定义，引用百度百科

容斥原理_百度百科

现在，假定已经能够熟悉这个原理的基本内容，下面是对容斥原理的一些解释。

为了方便说明，我们把全集设为三个集合的并集A1， A2， A3

我们要求全集的基数，由容斥原理的定义可知，我们可以对单独的子集求基数，然后再减去多计算的部分即可。

很简单的两步

1.每个集合基数单独计算

2.将多减去的部分加上即可

对于容斥原理的难点，主要是第二部分。

我们会发现，在执行第二步的时候，会多减去一部分，也有可能不多减，这是子集的交集为空集的情况，然后我们会发现，我们又多加了一部分，然后依次递归，直到最后的交集是所有子集的交集的情况，因为这样的时候，前面所有的多加多减去的部分已经计算完成，只剩下最后的这一部分。

我们看这个公式

https://bkimg.cdn.bcebos.com/formula/c14b2ae75dc2656967cb2e2dedbe57cd.svg

这个公式即是对上述所说的解释。

对于(-1)^m-1这里，可以说明以下。

对于两个子集的时候，只需要减去多加的部分，即| A1交A2 |

对于三个子集的时候，在减去多加的部分的同时，怎么保证A1， A2， A3的交集不为空？

它肯定有空的时候，这是毫无疑问的，但是也有不为空的时候，这也是毫无疑问的。

那既然有不为空的时候，那怎么保证两两子集交集不会与A1，A2，A3的交集重合？既然这样，就会有多减的时候，那么再将多减去的再加回来即可。

为用数学公式统一，那么无论如何都加一下不就可以了吗？

对于四个子集的时候，怎么保证对于每三个子集交集不会有与四个子集的交集重复的情况，那这是不是又多减去了一部分？

......

上述即是 (-1)^m-1的正确性

方便使用数学的公式统一，可以更精简的写成这种形式

https://bkimg.cdn.bcebos.com/formula/8235e8b08ec7fc0c668a225a1146711b.svg

一些应用

求解欧拉函数

欧拉函数的定义是，小于n并且与n互素的数从的个数

首先任何一个自然数，都能分解为素数的乘积形式，并且，有且只有一种情况。

比如10可以分解为2*5，既然这样，任何能被5和2整除的数和10都不能为素数。

那么全集就是1-10所有自然数，应用容斥原理。

要从U中寻找和10互素的数，可以用全集的基数减去是2 倍数的数5两个子集

A：2的倍数

B：5的倍数

ans = 9 - 4 - 1 + 0 = 4

验证：1 3 7 9

正确

推广形式

对于一个自然数n，可以将其拆分为这样的形式

Ai为i倍数组成的集合

然后有

用～A表示补集 |__| 表示向下取整

F(n) = |～A1 交 ～A2 ... 交～Ak|

可计算 |Ai| = |_n/pi_|

所以

|Ai 交Aj| = |_n/pi*pj_|

 经过一系列计算可得（不写过程了，电脑上打公式属实折磨）

最后得出的结论

F(x)  = n(1 - 1/p1)(1- 1/p2) ... (1 - 1/pk)