丑数 III

难度: Medium

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的 正整数 。

示例 1：

输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。

示例 2：

输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。

示例 3：

输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。

示例 4：

输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
输出：1999999984

提示：

1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
本题结果在 [1, 2 * 10^9] 的范围内

Submission

运行时间: 22 ms

内存: 16.1 MB

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        ab, ac, bc, abc = lcm(a, b), lcm(a, c), lcm(b, c), lcm(a, b, c)
        
        f = lambda k: sum(k // x for x in (a, b, c)) - sum(k // x for x in (ab, ac, bc))
        
        q, r = divmod(n, f(abc) + 1)
        if r == 0:
            return q * abc
        return q * abc + bisect_left(range(abc + 1), r, key=f)

Explain

该题解使用了最小公倍数（Least Common Multiple, LCM）和二分查找的策略。首先，计算a, b, c两两之间以及三者的最小公倍数（ab, ac, bc, abc）。定义一个函数f(k)来计算小于或等于k的丑数数量，这是通过包含-排除原理计算得出的：单独计算k能被a, b, c整除的数的数量，减去k能被ab, ac, bc整除的数的数量。通过这个函数，可以快速计算出任意数k下的丑数数量。接着，使用二分查找方法在有效范围内搜索第n个丑数。首先通过abc整除周期估计位置，然后在周期内精确搜索。

时间复杂度: O(log(abc))

空间复杂度: O(1)

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        # 计算两两以及三个数的最小公倍数
        ab, ac, bc, abc = lcm(a, b), lcm(a, c), lcm(b, c), lcm(a, b, c)
        
        # 定义函数f来计算<=k的丑数数量
        f = lambda k: sum(k // x for x in (a, b, c)) - sum(k // x for x in (ab, ac, bc))
        
        # 通过abc的周期性质估计第n个丑数的位置
        q, r = divmod(n, f(abc) + 1)
        # 如果刚好整除，直接返回周期倍数
        if r == 0:
            return q * abc
        # 否则在周期内使用二分查找确定具体的数
        return q * abc + bisect_left(range(abc + 1), r, key=f)

Explore

这种方法基于组合数学中的包含-排除原理。首先单独计算k能被a, b, c整除的数的数量，是为了确定所有可能由a, b, c生成的丑数。然而，这样单独计算会导致那些同时能被两个或三个数整除的数被重复计算多次。例如，一个数如果同时能被a和b整除，那么它在计算能被a整除的数和能被b整除的数时会被计算两次。因此，我们需要减去这些重复计算的部分，即减去k能被ab, ac, bc整除的数的数量。最后，如果一个数能同时被a, b, c三个数整除，我们在前面的步骤中减少了过多（实际上减了三次），因此还需要再加回来，这就是为什么还要考虑三个数的最小公倍数abc的原因。

为了确保二分查找的正确性，首先估计一个周期（由最小公倍数abc定义），在这个周期内，丑数的数量是固定的。通过计算整个周期内的丑数数量，可以快速定位到第n个丑数可能所在的大致范围。如果通过这个周期的计算，第n个丑数落在某个周期的边界上，可以直接返回周期的整数倍。如果不在边界上，那么就在该周期内使用二分查找。二分查找的过程中，通过不断调整搜索的上下界，直到找到确切的第n个丑数。这一过程中，必须仔细处理每次的上下界调整，确保不会错过任何可能的丑数，并且在达到终止条件时能正确停止。

二分查找的起始点和结束点的选择基于对问题的理解和周期性特征的利用。起始点通常设置为周期的开始，即0或者周期的最小值，而结束点则设置为一个周期的长度，即最小公倍数abc。选择这个范围的原因是，通过前面的计算和理论分析，我们知道一个周期内会包含所有可能的丑数类型，且数量固定。因此，一个周期的范围足以覆盖所有需要考察的情况，以确定具体的第n个丑数在哪里。通过设置这样的范围，我们可以有效地利用二分查找，减少不必要的计算，同时确保搜索的准确性。