1201. 丑数 III

题目描述

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

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

思路

丑数的定义见 263. 丑数，在这里就是只包含质因数 a、b 和 c 的正整数。我们可不可以像 264. 丑数 II 或 313. 超级丑数那样使用动态规划去做呢？考虑到 n 最大可用取到 10^9，如果建立 dp 数组一定会 OOM，因此只能去选择别的方法。

仔细想想，我们可以将问题简化。假设 a,b,c 的最小公倍数为 m，那么根据容斥原理，m 以内的丑数有

$$\text{ugly}(m)=\frac{m}{a}+\frac{m}{b}+\frac{m}{c}-\frac{m}{a\times b}-\frac{m}{a\times c}-\frac{m}{b\times c}+\frac{m}{a\times b\times c}$$

个，我们一定能将 n 分解为 n=l*ungly(m)+k，那么这样我们只需要求 ugly(m) 中的第 k 个数字即可。

那换个思路，假设将确定的 m 换成变量 x，x 以内的丑数是否也可以用上述公式计算呢？当然可以，那么求第 n 个丑数的问题实际上可以转换成一个二分搜索问题，我们求第 n 个丑数的最左边界即可。

这样按照题目要求，左右边界分别为 1, 2*10^9。我们每次使用一个检查函数去检查中间值是否大于 n，如果大于了就缩小右边界，否则扩大左边界。

最终代码为：

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        ab, ac = lcm(a, b), lcm(a, c)
        bc, abc = lcm(b, c), lcm(a, b, c)
 
        def check(num):
            cnt = num//a+num//b+num//c-num//ab-num//ac-num//bc+num//abc
            return cnt >= n
 
        l, r = 1, 2*10**9+1
        while l <= r:
            mid = l + (r-l)//2
            if check(mid):
                r = mid-1
            else:
                l = mid+1
        return l

想得太多

参考评论区，这道题是 878. 第 N 个神奇数字的升级版。

因为我们是要找最左边界，因此可以参考搜索模板，将最右端保守缩减：

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        ab, ac = lcm(a, b), lcm(a, c)
        bc, abc = lcm(b, c), lcm(a, b, c)
 
        def check(num):
            cnt = num//a+num//b+num//c-num//ab-num//ac-num//bc+num//abc
            return cnt >= n
 
        l, r = 1, 2*10**9+1
        while l < r:
            mid = l + (r-l)//2
            if check(mid):
                r = mid
            else:
                l = mid+1
        return l

注意此时判断条件为 l<r。