1201. 丑数 III -- 巧用二分搜索

1201. 丑数 III

class Solution:
	"""
    巧用二分搜索
    1201. 丑数 III
    https://leetcode.cn/problems/ugly-number-iii/
    """
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        # 题目说本题结果在 [1, 2 * 10^9] 范围内
        left, right = 1, 2e9
        # 搜索左侧边界的二分搜索 左闭右闭 [left, right]
        while left <= right:
            mid = left + (right-left)//2
            if self.f(mid, a, b, c) >= n:
                right = mid - 1
            else:
                left = mid + 1

        return int(left)

    def f(self, num, a, b, c):
        """
        函数 f 是一个单调函数, 随着num的增加而增加
        计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
        :param num:
        :param a:
        :param b:
        :param c:
        :return:
        """
        set_a = num // a
        set_b = num // b
        set_c = num // c

        set_ab = num // lcm(a, b)
        set_ac = num // lcm(a, c)
        set_bc = num // lcm(c, b)

        set_abc = num // lcm(lcm(a, b), c)
        # 集合论定理：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
        return set_a + set_b + set_c - set_ac - set_ab - set_bc + set_abc


# 求两个数的最大公约数（greatest common divisor），辗转相除法
def gcd(a, b):
    # 保证a>b
    if a < b:
        return gcd(b, a)

    if b == 0:
        return a

    return gcd(b, a % b)


# 求两个数的最小公倍数（least common multiple）
def lcm(a, b):
    return a * b/gcd(a, b)

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59