容斥原理在我们的高中数学中由了解过，就是两个集合A，B的并集的元素个数。同样，在大学里的概率论中也会讲解。

  在概率论中,我们有这样的一个公式：

如图：

由于A与B有重叠部分，所以A+B后要减去一次重叠的部分（A∩B）。

如图： 很明显，E，F，G三个部分分别重叠了两次，所以我所我们要减(A ∩ B) ，(A ∩ C) ，(B ∩ C)，但也相当于减了三次G部分(A ∩ B ∩ C)，所以我们还要在加一次(A ∩ B ∩ C)。

以此类推。

推荐专栏： 算法零基础100讲》(第14讲)最小公倍数

  由于今日的题解需要用到最小公倍数，所以我们需要回顾一下，最小公倍数的计算方法。通过定理我们可以很明确的知道，a和b的最小公倍数就等于(a * b) / gcd(a，b)。

题目链接： 1201. 丑数 III

思路分析：   题目要求我们找出第n个丑数，而题目给定丑数的定义为，能够被a，b，c，整除的数。所以我们最容易想到的就是暴力枚举，从1开始枚举，当遇到a，b，c的约数时，便记录下来，直到找到第n位。 代码如下：

但题目给定的数据范围为[1，2000000000]，很明显暴力的解法会超时，而这种时候我们就得想到一种时间复杂度更快的方法，所以我们很容易会想到O(logn)的二分法，但是这种解法与该题由上面联系呢？

接下来我们进行进一步的分析。

  现在我们假设ab , ac , bc分别为a和b，a和c，b和c的最小公倍数，abc为a,b,c的最小公倍数，假设他们不大于n丑数有m个，则m = n / a + n / b + n / c - n / ab - n / ac - n / bc + n / abc。   有了上面的m，我们在结果区间[1，2000000000]上取中间值mid，计算不大于mid的丑数有m个，我们便可以对m与题目所给的n(这里的n是题目给的n)进行比较，如果m < n则说明小于mid的丑数还不够n个，那么我们就需将mid增大，便将区间转化为[mid + 1，2000000000]，在从中找出新的mid，继续进行比较，直到区间重合，此时的区间值就是我们所求的第n个丑数的值。

代码如下：