LeetCode 1201. 丑数 III

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节
标签
数学 二分查找 组合数学 数论

题目描述

✅ 1201. 丑数 III

image-20260928230314633

image-20260928230314634

题意分析

本题把能被 a、b、c 中至少一个整除的正整数称为丑数，要求它们从小到大排列后的第 n 个。一个数即使同时满足多个整除条件，也只能计一次。

n 很大，不适合逐个生成。可以反过来问：不超过某个值 x 的丑数有多少个？若数量达到 n，第 n 个丑数就不会超过 x。

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

核心思路

[!blue]

不超过 x 的 a 的倍数有 x / a 个，这里的除法向下取整。分别统计三个因子的倍数后，公倍数会重复出现；同时被两个因子整除，等价于被它们的最小公倍数整除。

记两两最小公倍数为 ab、ac、bc，三个因子的最小公倍数为 abc，则 count(x) = x/a + x/b + x/c - x/ab - x/ac - x/bc + x/abc。只满足一个条件的数保留一次；满足两个条件的数先加两次再减一次；满足三个条件的数先加三次、减三次，最后补回一次。因此计数既不重复也不遗漏。

count(x) 随 x 增大不会减少，可以二分第一个满足 count(x) >= n 的位置。计数达标时答案在 mid 或它左边，令 right = mid；未达标时答案一定更大，令 left = mid + 1。两端相遇时就是最小达标值，它自身必须使计数增加，因此正好是第 n 个丑数。

用 lcm(x, y) = x / gcd(x, y) * y 预处理公倍数，并使用 64 位整数。题目保证 a * b * c <= 10^18，所以这些最小公倍数及先除后乘的中间量都在范围内；计数也用宽整数，避免多个商相加时溢出。

解题步骤

  1. 计算 ab、ac、bc，再用 lcm(ab, c) 得到 abc。
  2. 题目保证答案位于 [1, 2 * 10^9]，以此作为二分区间。
  3. 每轮用容斥公式统计不超过 mid 的丑数数量，按是否达到 n 缩小区间。
  4. 当 left == right 时返回该值。即使中途计数恰好等于 n，也要继续向左找，不能直接返回计数平台中的任意位置。

代码实现

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+1)+\log(A+1))$，U 为答案上界、A 为输入因子的最大值，包含最大公约数预处理。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 容斥自然处理相等因子与互相整除，无需额外去重分支。
  • 使用宽整数保存计数和最小公倍数。

易错点总结

[!yellow]

  • 只加单项计数，会把公倍数重复统计。
  • 减两两交集后不补三重交集，会把三者公倍数删掉。
  • 计数刚好相等就直接返回，可能停在计数平台而非首个达标值。

相似题目

题目 难度 关联与区别
878. 第 N 个神奇数字 困难 由两个除数推广为三个除数，阈值计数需要完整容斥后再二分第n项。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2020/72740829
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！