LeetCode 1201. 丑数 III

2020-07-03 HGNULB 约 12 分钟

文章信息 6 个分类 8 个标签

分类

题目描述

✅ 1201. 丑数 III

题意分析

这里的「丑数」被重新定义了：只要能被 a、b、c 中至少一个整除的正整数就算丑数。注意它和 264 题那种「质因数只含 2、3、5」的定义完全不同——本题不要求因数分解，只要求整除，所以丑数在数轴上的分布是三个等差数列的并集。要求返回第 n 个丑数。

约束是解题的最强信号：n、a、b、c 都可以取到 $10^9$，而题目又保证答案不超过 $2 \times 10^9$。前者直接否决了「从 1 开始逐个判断」和「用堆逐个生成前 n 个」这类做法——它们的复杂度至少是 $O(n)$ 或 $O(n \log n)$，$10^9$ 次循环必然超时。后者则暗示答案落在一个已知且不大的值域区间里，于是「在值域上做文章」成了唯一出路。

再看一个关键的结构性事实：虽然「第 n 个丑数是多少」不好直接算，但反过来问「不超过 x 的丑数有几个」却很好算——被 a 整除的有 $\lfloor x/a \rfloor$ 个，三个数列各自的个数都是一除就得。真正的麻烦只在于三个数列有交集，同一个数会被数好几遍，需要去重。正问题难、反问题易，且反问题的答案随 x 单调不减，这是本题最重要的信号。

边界上要留意两处：三个数的公倍数在最坏情况下能到 $10^{18}$ 量级，远超 32 位整数，中间量必须用 64 位；a、b、c 可能相等或互相整除（比如 a = 2, b = 4），此时数列高度重叠，去重逻辑必须仍然成立。

解法：二分答案 + 容斥计数

核心思路

暴力做法是从 1 开始逐个数：判断 i % a == 0 || i % b == 0 || i % c == 0，数够 n 个就返回。瓶颈非常直接——循环次数等于答案本身，最坏 $2 \times 10^9$ 次，必然超时。换成「三指针合并三个数列」或者「小根堆逐个吐出丑数」也只是把常数改小，循环次数依旧是 $O(n)$，本质没变。

观察：我们其实不需要逐个走到第 n 个丑数，只需要判定某个候选值是不是够格。定义 $f(x)$ 为「不超过 x 的丑数个数」，那么第 n 个丑数就是最小的满足 $f(x) \ge n$ 的 x。这个转化之所以成立，是因为 $f$ 随 x 单调不减：x 变大只会让丑数集合变大，个数不会减少。有了单调性，就可以在值域 $[1, 2 \times 10^9]$ 上二分，把 $O(n)$ 的枚举压成 $O(\log U)$ 次判定。

二分不变量：区间 [left, right] 始终包含答案，即 $f(\text{left} - 1) < n \le f(\text{right})$。每轮取 mid，若 $f(mid) \ge n$ 则答案在 [left, mid]（mid 自己可能就是答案，所以 right = mid 而不是 mid - 1）；否则答案在 [mid + 1, right]。循环到 left == right 时区间只剩一个数，它就是最小可行值。

剩下的问题是把 $f(x)$ 算准。三个集合求并集的大小，正是容斥原理的标准场景：先把三个集合各自的大小加起来，此时两两重叠的部分被数了两次、三重重叠的部分被数了三次；减去三个两两交集后，三重重叠的部分被减成了 $3 - 3 = 0$ 次，所以还要再加回来一次。而「同时被 a 和 b 整除」等价于「被 $\mathrm{lcm}(a,b)$ 整除」，于是 $f(x) = \lfloor x/a \rfloor + \lfloor x/b \rfloor + \lfloor x/c \rfloor - \lfloor x/\mathrm{lcm}(a,b) \rfloor - \lfloor x/\mathrm{lcm}(a,c) \rfloor - \lfloor x/\mathrm{lcm}(b,c) \rfloor + \lfloor x/\mathrm{lcm}(a,b,c) \rfloor$，式中所有除法都是向下取整。这个公式对 a、b、c 有重复或互相整除的情况同样成立——例如 a = 2, b = 4 时 $\mathrm{lcm}(a,b) = 4$，加上的 $\lfloor x/4 \rfloor$ 又被原样减掉，自动退化成两个集合的情形，不需要任何特判。

最小公倍数用 $\mathrm{lcm}(x,y) = x / \gcd(x,y) \times y$ 计算，gcd 用辗转相除法手写。注意必须先除后乘，先乘会凭空多出一次可能溢出的中间量。

解题步骤

预处理四个最小公倍数：ab、ac、bc 和三者的 abc。为什么提前算：它们在二分的每一轮里都要用到，而 gcd 是 $O(\log)$ 的，放进循环会白白多出一个对数因子；更重要的是提前算能让计数函数变成纯粹的常数时间除法。三者的 lcm 用 lcm(ab, c) 递推得到，因为 $\mathrm{lcm}(a,b,c) = \mathrm{lcm}(\mathrm{lcm}(a,b), c)$。

确定二分区间：左端取 1（答案至少是三者中的最小值，取 1 一定不会漏），右端取 2_000_000_000。为什么可以取这个常数：题目明确保证结果小于 $2 \times 10^9$，所以右端一定是可行解，二分的前提「区间内含答案」成立。若不放心，也可以用 min(a,b,c) * n 作为上界，但要防溢出。

二分主体用「找第一个可行解」的写法：条件成立时 right = mid，不成立时 left = mid + 1，循环条件是 left < right。为什么 right = mid 不能写成 mid - 1：我们要的是最小的可行值，mid 本身可行时它就是候选答案，减一会把答案排除在区间外。这个写法天然不会死循环，因为 mid 向下取整时永远满足 mid < right，两个分支都会真正缩小区间。

计数用容斥公式：三个单项相加、三个两两 lcm 项相减、一个三重 lcm 项加回。为什么必须减去两两交集：不减的话像 6（同时被 2、3 整除）这样的数会被数两次，$f$ 被高估，二分会收敛到一个偏小的值。

全程用 64 位：lcm 最大可达 $10^{18}$ 量级，mid 也接近 $2 \times 10^9$，都超出了 32 位范围。返回时再强转回 int。

返回 left：循环退出时 left == right，由不变量可知它就是最小的满足 $f(x) \ge n$ 的值。

以 n = 5, a = 2, b = 11, c = 13 走一遍（丑数序列是 2, 4, 6, 8, 10, 11, 12, ...，答案应为 10）。

预处理：ab = lcm(2,11) = 22，ac = lcm(2,13) = 26，bc = lcm(11,13) = 143，abc = lcm(22,13) = 286。

初始 left = 1，right = 2000000000。前若干轮 mid 都极大，$f(mid)$ 远大于 5，区间不断向左折半；快进到 left = 1, right = 15 这一段来看细节。

mid = 8：$f(8) = 8/2 + 8/11 + 8/13 - 8/22 - 8/26 - 8/143 + 8/286 = 4 + 0 + 0 - 0 - 0 - 0 + 0 = 4 < 5$，说明 8 以内不够 5 个，答案在右边，left = 9。

mid = 12（区间 [9, 15]）：$f(12) = 6 + 1 + 0 - 0 - 0 - 0 + 0 = 7 \ge 5$，可行，right = 12。

mid = 10（区间 [9, 12]）：$f(10) = 5 + 0 + 0 - 0 - 0 - 0 + 0 = 5 \ge 5$，可行，right = 10。

mid = 9（区间 [9, 10]）：$f(9) = 4 + 0 + 0 = 4 < 5$，不可行，left = 10。

此时 left == right == 10，退出循环，返回 10。可以验证 10 本身确实是丑数——这不是巧合：若 x 是最小的满足 $f(x) \ge n$ 的数，则 $f(x-1) < f(x)$，说明 x 自己被计入了，它必然是丑数。

代码实现

class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        long ab = lcm(a, b);
        long ac = lcm(a, c);
        long bc = lcm(b, c);
        long abc = lcm(ab, c);

        long left = 1;
        long right = 2_000_000_000L;
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (countNotGreater(mid, a, b, c, ab, ac, bc, abc) >= n) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return (int) left;
    }

    private long countNotGreater(long limit, int a, int b, int c, long ab, long ac, long bc, long abc) {
        // 容斥计数避免同时被多个因子整除的数重复统计。
        return limit / a + limit / b + limit / c
            - limit / ab - limit / ac - limit / bc
            + limit / abc;
    }

    private long lcm(long x, long y) {
        return x / gcd(x, y) * y;
    }

    private long gcd(long x, long y) {
        while (y != 0) {
            long rem = x % y;
            x = y;
            y = rem;
        }
        return x;
    }
}

func nthUglyNumber(n int, a int, b int, c int) int {
    ab := lcm(int64(a), int64(b))
    ac := lcm(int64(a), int64(c))
    bc := lcm(int64(b), int64(c))
    abc := lcm(ab, int64(c))

    left := int64(1)
    right := int64(2_000_000_000)
    for left < right {
        mid := left + (right-left)/2
        if countNotGreater(mid, int64(a), int64(b), int64(c), ab, ac, bc, abc) >= int64(n) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return int(left)
}

func countNotGreater(limit int64, a int64, b int64, c int64, ab int64, ac int64, bc int64, abc int64) int64 {
    // 容斥计数避免同时被多个因子整除的数重复统计。
    return limit/a + limit/b + limit/c - limit/ab - limit/ac - limit/bc + limit/abc
}

func lcm(x int64, y int64) int64 {
    return x / gcd(x, y) * y
}

func gcd(x int64, y int64) int64 {
    for y != 0 {
        rem := x % y
        x = y
        y = rem
    }
    return x
}

复杂度分析

时间复杂度：$O(\log U)$，其中 $U = 2 \times 10^9$ 是答案上界，约 31 轮。凭什么：预处理四个 lcm 各需一次辗转相除，是 $O(\log \max(a,b,c))$ 的一次性开销；二分每轮只做 7 次整除和 6 次加减，是常数时间，与 n 的大小完全无关——这正是把 $O(n)$ 枚举换成值域二分的收益。

空间复杂度：$O(1)$。凭什么：全程只用了四个 lcm 变量和三个二分变量，没有任何与输入规模相关的数组或递归栈。

关键点总结

「求第 k 小」难而「数出不超过 x 的有几个」易，且计数函数单调——满足这两条就应该条件反射地想到二分答案。这是 668、719、878 等一大批题的共同骨架，面试时应当先说出这个判定框架，再谈具体怎么计数。

二分的对象是答案的取值而不是数组下标，因此上下界要从题目约束里找。本题直接给了「答案小于 $2 \times 10^9$」，这种提示在题面里出现时几乎是在明说二分答案。

求多个集合的并集大小，用容斥原理：奇数重交集加、偶数重交集减。而「同时被若干数整除」等价于「被它们的最小公倍数整除」，这一步转换是数论题里的通用桥梁。

「找第一个满足条件的位置」固定写成 while (left < right) + 条件成立时 right = mid，写熟这一个模板比每次现推边界更可靠。收敛后 left == right，且该位置本身一定是可行解。

涉及乘法或最小公倍数时先估算数量级：本题 $\mathrm{lcm}$ 可达 $10^{18}$，必须用 64 位并且 lcm 要先除后乘。面试时主动提一句溢出风险是加分项。

易错点总结

写成 x * y / gcd(x, y)：a = 999999937, b = 999999999 时 x * y 接近 $10^{18}$，若在 32 位下计算直接溢出为负；即使用 64 位，三重 lcm 再乘一次也可能超过 long 上界。正确写法是 x / gcd(x, y) * y，先除保证中间量不膨胀。

用 int 存 mid 或 lcm：right 初值 $2 \times 10^9$ 已经超过 int 上限 $2147483647$ 的安全区，a = 2, b = 3, c = 5 时 abc = 30 看不出问题，但 a = 1000000000, b = 999999999 时 ab 直接溢出成负数，容斥项变成负除法，计数结果荒谬。

忘记减两两交集：n = 4, a = 2, b = 3, c = 4 时若只算 $\lfloor x/2 \rfloor + \lfloor x/3 \rfloor + \lfloor x/4 \rfloor$，x = 6 会被算成 $3+2+1=6$ 个，而真实丑数只有 2,3,4,6 四个，计数被高估，二分收敛到 4 而正确答案是 6。

减了两两交集却忘记加回三重交集：a = 2, b = 3, c = 5 时 x = 30 被三个集合同时包含，加三次减三次后计数为 0 次，$f$ 被低估，二分向右跑过头，返回一个偏大的数。

right = mid - 1 配合 left < right：n = 5, a = 2, b = 11, c = 13 时当 mid = 10 满足条件却把 right 压到 9，答案 10 被挤出区间，最终返回 9，而 9 根本不是丑数。

循环条件写成 left <= right 但分支仍用 right = mid：mid 等于 left 时 right 被赋成同一个值，区间不再缩小，直接死循环 TLE。「找第一个」的模板必须整套照搬，不能混用。

上界取 n * min(a,b,c) 却不防溢出：n = 1000000000, a = 1000000000 时乘积是 $10^{18}$，在 int 下溢出为负，二分区间直接非法，返回 1 或死循环。要么用题目保证的 $2 \times 10^9$，要么老实用 64 位。

把丑数理解成「质因数只含 a、b、c」：a = 2, b = 3, c = 5 时按 264 题的定义 7 不是丑数、8 是；但按本题定义 8 是（被 2 整除）、9 是（被 3 整除）、7 不是。两种定义在这组数据上恰好接近，换成 a = 4 就会立刻分叉——2 在本题里不是丑数，在 264 的定义里却是。

改用堆逐个生成前 n 个丑数：n = 1000000000 时循环要跑 $10^9$ 轮并伴随 $\log$ 级堆操作，必然超时；这个做法只适用于 264 题那种 n ≤ 1690 的规模。

提前判断 mid 是否为丑数并特殊处理：完全没有必要，且容易写出 while (mid % a != 0 && ...) mid-- 这类回退循环，最坏退化成线性扫描。最小可行解自动就是丑数，无需额外校正。

相似题目

题目	难度	考察点
878. 第 N 个神奇数字	困难	本题的两因子版本，容斥只有三项，但要对结果取模
264. 丑数 II	中等	定义是「质因数只含 2、3、5」，`n` 很小，用三指针递推而不是二分
668. 乘法表中第k小的数	困难	同为值域二分，计数改为逐行统计 $\min(n, x/i)$，不涉及容斥
719. 找出第 K 小的数对距离	困难	二分距离，计数需先排序再用双指针，判定函数本身是 $O(n)$
378. 有序矩阵中第 K 小的元素	中等	二分值域，利用矩阵行列有序沿阶梯线计数，也可用堆做多路归并
875. 爱吃香蕉的珂珂	中等	二分的是「速度」这种非答案量，判定函数是耗时求和而非计数
410. 分割数组的最大值	困难	二分最大段和，判定用贪心切分，属于「最小化最大值」而非「求第 k 小」
1482. 制作 m 束花所需的最少天数	中等	二分天数，判定是连续段扫描，展示了二分答案在非数论场景下的同一套写法