题目地址

解题思路

本题的关键还是在于求$f(mid)=count$（数字在范围[1,mid]区间，包含的丑数个数为count）

比如：

输入：n = 3, a = 2, b = 3, c = 5
此时就有：$f(1)=0$，$f(2)=1$，$f(3)=2$，$f(4)=3$，$f(5)=3$

可以看到，这个函数是一个单调不递减的，有单调性自然就可以用二分搜索了。

容斥原理

根据容斥原理，可以列出此方程为:

$f(mid)=mid / a + mid / b + mid / c - mid / lcm\underline{\hspace{.05in}}{ab} - mid / lcm\underline{\hspace{.05in}}{ac} - mid / lcm\underline{\hspace{.05in}}{bc} + mid / lcm\underline{\hspace{.05in}}{abc}$

其中lcm表示最小公倍数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import math

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:

        # 最小公倍数
        def lcm(x, y):
            return x * (y // math.gcd(x,y))

        lcm_ab = lcm(a, b)
        lcm_ac = lcm(a, c)
        lcm_bc = lcm(b, c)
        lcm_abc = lcm(lcm_ab, c)

        left = 1
        right = min(a,b,c) * n + 1
        while left <= right:
            mid = left + (right - left) // 2
            count = mid // a + mid // b + mid // c - mid//lcm_ab - mid//lcm_ac - mid // lcm_bc + mid // lcm_abc
            if count < n:
                left = mid + 1
            else:
                right = mid - 1
        return left