LeetCode 878. 第 N 个神奇数字

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
数学 二分查找

题目描述

✅ 878. 第 N 个神奇数字

image-20260929105049921

题意分析

能被 a 或 b 整除的正整数都是神奇数字，同时被两者整除也只算一个。将这些不同数字从小到大排列，求第 n 个，再对 10^9 + 7 取模返回。

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

核心思路

[!blue]

n 可能很大，逐个生成神奇数字不合适。换一个方向：对候选数 x，如果能快速知道不超过它的神奇数字有多少，就能判断第 n 个数字在它左侧还是右侧。

不超过 x 的 a 的倍数有 x / a 个，b 的倍数有 x / b 个。两部分都包含最小公倍数 lcm 的倍数，直接相加会重复计数，因此由容斥得到 count(x) = x / a + x / b - x / lcm，其中除法向下取整。

随着 x 增大，计数不会减少。于是答案就是第一个满足 count(x) >= n 的整数，可以二分这个真假分界。这个整数一定自身是神奇数字：否则从 x - 1 到 x 没有新增合法数，不可能恰好在这里首次达到 n。

搜索范围取 [1, n * min(a, b)]。较小因子的前 n 个倍数已经提供了 n 个不同神奇数字，所以右端一定不小于答案。若中点计数达到 n，答案可能就是中点，也可能更小，令 hi = mid；否则中点及左侧都不够，令 lo = mid + 1。两端相遇时得到最小可行值。

解题步骤

  1. 用最大公约数计算最小公倍数。
  2. 在一到 n×min(a,b) 之间二分。
  3. 计数不少于 n 时保留左半区，否则排除中点及其左侧。
  4. 得到真实答案后再取模返回。

最小公倍数用 a / gcd(a, b) * b 计算，边界、计数和乘法都使用宽整数。若 a == b 或一者整除另一者，容斥公式仍会自动去重，无需额外分支。取模只影响输出，不能提前用于二分中的大小比较。

代码实现

class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        long mod = 1_000_000_007L;
        long g = gcd(a, b);
        long l = (long) a / g * b;

        long lo = 1;
        // 前 n 个较小因子的倍数已经提供 n 个合法数，作为安全上界。
        long hi = (long) n * Math.min(a, b);

        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            // 两个倍数集合相加后，减去最小公倍数对应的重复项。
            long cnt = mid / a + mid / b - mid / l;

            if (cnt >= n) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        return (int) (lo % mod);
    }

    private long gcd(long x, long y) {
        while (y != 0) {
            long t = x % y;

            x = y;
            y = t;
        }

        return x;
    }
}

func nthMagicalNumber(n int, a int, b int) int {
    const mod int64 = 1_000_000_007
    g := gcd(int64(a), int64(b))
    l := int64(a) / g * int64(b)

    lo := int64(1)
    // 前 n 个较小因子的倍数已经提供 n 个合法数，作为安全上界。
    hi := int64(n) * int64(min(a, b))
    for lo < hi {
        mid := lo + (hi-lo)/2
        // 两个倍数集合相加后，减去最小公倍数对应的重复项。
        cnt := mid/int64(a) + mid/int64(b) - mid/l
        if cnt >= int64(n) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return int(lo % mod)
}

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

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：$O(\log(n\min(a,b)+1))$，每轮常数次除法，最大公约数预处理在同阶上界内。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 容斥负责去掉同时满足两个整除条件的重复数。
  • 二分寻找首次达到，不是任意一个计数为 n 的位置。
  • 上界乘法先提升为宽整数，比较过程中不取模。

易错点总结

[!yellow]

  • 计数不减最小公倍数项：重复倍数被算两次。
  • 乘法完成后才转宽类型：原类型中已经发生溢出。
  • 二分过程中对数值取模：破坏大小关系和计数含义。
  • 不可行时仍令左界等于 mid：相邻边界时可能无法收缩。

相似题目

题目 难度 关联与区别
1201. 丑数 III 中等 本题判断能被a或b整除，原题扩展为三个除数，都可用容斥计数配合答案二分。
668. 乘法表中第k小的数 困难 同样无需生成全部候选，只要能统计不超过某值的候选数量就可定位第n项。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/50743524
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！