LeetCode 878. 第 N 个神奇数字
目录
题目描述
题意分析
一个正整数如果能被
a整除或能被b整除，就叫「神奇数字」。把所有神奇数字从小到大排好，问第n个是多少，结果对 $10^9 + 7$ 取模。约束是全题最重要的信号：
n最大 $10^9$，而a、b最大只有 $4 \times 10^4$。这意味着答案的量级在 $n \cdot \min(a,b)$ 附近，也就是 $4 \times 10^{13}$——远超int，必须全程用 64 位整数。同时n高达十亿，任何逐个枚举神奇数字的做法都不可能，哪怕是双指针合并两个等差数列也要走 $10^9$ 步。「取模」这个要求也值得警惕：它只作用于最终答案，中间的比较和计数绝不能取模。一旦中途取模，数值的大小关系就被破坏，二分的单调性直接失效。
换个角度看目标：与其问「第
n个是谁」，不如问「小于等于某个数x的神奇数字有几个」。后者有闭式解，而且随x单调不减——这正是二分答案的标准形状。边界：
a与b可能相等，也可能互为倍数（如a = 2、b = 4），此时两个集合大量重叠，计数时必须扣除重复；n = 1时答案是min(a, b)。
解法：二分答案 + 容斥计数
核心思路
朴素做法是用两个指针分别在
a, 2a, 3a, ...和b, 2b, 3b, ...上归并，跳过重复项，数到第n个为止。逻辑正确，但要走n步，$n = 10^9$ 时必然超时。瓶颈在于我们在「一个一个地生成答案」。而真正的突破口是：判断一个候选答案是否够大，比生成答案容易得多。
定义 $f(x)$ 为区间 $[1, x]$ 内神奇数字的个数。$[1, x]$ 里
\[f(x) = \left\lfloor \frac{x}{a} \right\rfloor + \left\lfloor \frac{x}{b} \right\rfloor - \left\lfloor \frac{x}{\mathrm{lcm}(a,b)} \right\rfloor\]a的倍数有 $\lfloor x/a \rfloor$ 个、b的倍数有 $\lfloor x/b \rfloor$ 个，但同时是两者倍数的数被算了两次——它们恰好是 $\mathrm{lcm}(a,b)$ 的倍数，共 $\lfloor x/\mathrm{lcm}(a,b) \rfloor$ 个。由容斥原理：这个函数 $O(1)$ 可算，且关于
x单调不减。于是问题变成：求最小的x使得 $f(x) \ge n$。这个最小的x一定本身就是神奇数字——因为若x不是神奇数字，则 $f(x) = f(x-1)$，x-1也满足条件，与「最小」矛盾。不变量：二分维持左闭右闭区间
[lo, hi]，答案始终落在其中，即 $f(lo - 1) < n \le f(hi)$。每轮取中点mid，若 $f(mid) \ge n$ 说明答案不会超过mid，令hi = mid（保留mid，它可能就是答案）；否则mid太小，令lo = mid + 1。区间每轮至少减半，lo == hi时收敛到唯一解。上界怎么定？第
n个神奇数字一定不超过 $n \cdot \min(a, b)$——因为 $\min(a,b)$ 的前n个倍数本身就是n个互不相同的神奇数字。取这个值作hi既安全又不会太松。最小公倍数用 $\mathrm{lcm}(a,b) = a / \gcd(a,b) \times b$ 计算，先除后乘是为了避免
a * b中间结果溢出。gcd用辗转相除，几行循环即可。
解题步骤
- 先算
g = gcd(a, b)与l = a / g * b：l是容斥里要扣除的那一项的周期。写成a / g * b而不是a * b / g，是因为前者的中间值不超过l本身，后者在a、b都取 $4 \times 10^4$ 时虽然还不会爆long，但换成更大的数据就有风险，养成先除后乘的习惯。- 二分区间取
lo = 1、hi = (long) n * min(a, b)：下界取 1 是因为答案至少是min(a,b) >= 2；上界的构造理由见上。(long)强转必须写在乘法之前，否则n * min(a,b)先按int算就溢出了。- 循环条件
lo < hi：配合「hi = mid/lo = mid + 1」这套收缩方式，退出时lo == hi即为答案，不需要在循环外再做一次判断。若写成lo <= hi并用hi = mid，区间不再收缩，会死循环。- 中点用
lo + (hi - lo) / 2：lo与hi都可能接近 $4 \times 10^{13}$，直接(lo + hi) / 2虽然在long下不会溢出，但这个写法是通用习惯，换成边界更大的题就是必须的。同时向下取整保证mid < hi，配合hi = mid才能真正缩小区间。- 计数
cnt = mid / a + mid / b - mid / l：整数除法天然向下取整，正是我们要的 $\lfloor \cdot \rfloor$。这里绝不能取模。cnt >= n时hi = mid，否则lo = mid + 1：注意是>=而不是==。神奇数字里没有重复，但 $f$ 是阶梯函数，很多个x都会给出同一个cnt，我们要的是使 $f(x) \ge n$ 的最左位置。- 返回
(int)(lo % mod)：取模只在最后一步做，且要先取模再转int。以
n = 4、a = 2、b = 3走一遍。神奇数字序列是 2, 3, 4, 6, 8, 9, …，第 4 个是 6。预处理：
g = gcd(2,3) = 1，l = 2 / 1 * 3 = 6。区间lo = 1、hi = 4 * 2 = 8。第 1 轮：
mid = 1 + (8-1)/2 = 4。f(4) = 4/2 + 4/3 - 4/6 = 2 + 1 - 0 = 3。3 < 4，说明 4 以内不够，lo = 5。区间变成[5, 8]。第 2 轮：
mid = 5 + (8-5)/2 = 6。f(6) = 6/2 + 6/3 - 6/6 = 3 + 2 - 1 = 4。4 >= 4，答案不超过 6，hi = 6。区间变成[5, 6]。注意这里容斥的作用：6 同时是 2 和 3 的倍数，若不减去6/6，会算成 5，直接把答案推到更小的位置。第 3 轮：
mid = 5 + (6-5)/2 = 5。f(5) = 5/2 + 5/3 - 5/6 = 2 + 1 - 0 = 3。3 < 4，lo = 6。区间变成[6, 6]。
lo == hi，退出循环，返回6 % (10^9+7) = 6，与手工枚举一致。再验证一下「答案必是神奇数字」：假如二分停在 5，那么
f(5) = 3 < 4，不满足条件，不可能成为最小解——阶梯函数只在神奇数字处上升，所以最左的满足点必然踩在台阶上。
代码实现
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;
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)
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 \cdot \min(a,b)))$，约 46 轮。区间长度 $4 \times 10^{13}$ 每轮减半，单轮的计数函数是 $O(1)$ 的三次除法；预处理的
gcd是 $O(\log \min(a,b))$，只算一次。- 空间复杂度：$O(1)$。只用了
g、l、lo、hi、mid、cnt几个 64 位标量；gcd写成迭代而非递归，连栈空间也省了。
关键点总结
- 「求第 k 小」而 k 极大、直接枚举不可行时，把问题翻转成「小于等于 x 的有几个」，再对 x 二分——这是二分答案最经典的触发条件。
- 计数函数必须关于候选值单调，二分才成立；本题的 $f(x)$ 是阶梯上升函数，单调性显然，这一点要在面试中明说。
- 「能被 a 或 b 整除」的计数一定伴随容斥：加两项、减 $\mathrm{lcm}$ 那项。忘了减就会把
a = 2, b = 4这类高度重叠的输入算爆。lcm用a / gcd * b而非a * b / gcd，先除后乘是防溢出的标准写法。- 取模只在返回前做一次。中间量一旦取模，比较就失去意义，二分会收敛到错误位置——凡是「带模数的求第 k 大/小」都要警惕这一点。
- 面试视角：这题的答题顺序应当是「先说 n 太大不能枚举 → 提出计数函数 → 写出容斥公式 → 确认单调性 → 二分模板」。能主动指出「最小的满足点必然是神奇数字」，说明真的理解了阶梯函数，是加分项。
易错点总结
- 计数时忘记减去 $\lfloor x/\mathrm{lcm} \rfloor$：
n = 4, a = 2, b = 4中f(8)会算成4 + 2 = 6而不是 4，二分提前收敛，返回 6 而正确答案是 8。- 中间结果取模：把
cnt或mid对 $10^9+7$ 取模后再比较，n = 10^9, a = 40000, b = 40000这类大答案会让mid绕回小值，单调性彻底破坏，结果随机。- 全程用
int：hi = n * min(a,b)在n = 10^9、min = 40000时是 $4 \times 10^{13}$，int溢出成负数，二分区间直接非法。(long)强转位置写错：写成long hi = (long)(n * Math.min(a, b))，乘法仍按int完成后才提升，溢出照旧发生。必须是(long) n * Math.min(a, b)。lcm写成a * b / g：a = 40000, b = 39999时a * b在int下溢出（约 $1.6 \times 10^9$ 已超int上限），得到负的lcm，容斥项变成加法。- 收缩写成
hi = mid - 1且循环条件lo < hi：n = 1, a = 2, b = 3中答案 2 会被跳过，lo与hi交错后返回 1，而 1 根本不是神奇数字。- 收缩写成
lo = mid且循环条件lo < hi：当mid恰好等于lo时区间不再变化，n = 2, a = 2, b = 2会死循环。- 判定写成
cnt == n：$f$ 是阶梯函数，很多个x给出同一个cnt，用等号会在f(mid) > n时既不进左也不进右，或者停在一个非神奇数字上，n = 4, a = 2, b = 3可能返回 7。- 上界取成
n * max(a, b)或干脆取Long.MAX_VALUE：前者只是多几轮无妨，后者会让mid / a之类的计算在极端值下仍安全，但lo + (hi - lo) / 2之外的写法（如(lo + hi) / 2）会溢出成负数。gcd递归实现且未处理y == 0：gcd(4, 0)若写成gcd(y, x % y)而不先判零，会触发除零异常；本题a、b均为正数，但习惯性的守卫应当保留。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1201. 丑数 III | 中等 | 本题推广到三个因子，容斥要展开成「加三减三加一」共七项 |
| 668. 乘法表中第k小的数 | 困难 | 计数函数变成逐行累加 $\min(k/i, n)$，无闭式解但仍 $O(m)$ 可算 |
| 719. 找出第 K 小的数对距离 | 困难 | 计数要先排序再用滑动窗口统计距离不超过 x 的数对，二分套双指针 |
| 875. 爱吃香蕉的珂珂 | 中等 | 二分的是「速度」，判定函数是耗时求和，单调性来自速度越大耗时越少 |
| 1011. 在 D 天内送达包裹的能力 | 中等 | 二分「运力」，下界必须取包裹最大值，边界推导是这题的主要考点 |
| 410. 分割数组的最大值 | 困难 | 与 1011 同构的最小化最大值，也可用区间 DP 解，适合对比两种范式 |
| 1482. 制作 m 束花所需的最少天数 | 中等 | 二分「天数」，判定要扫一遍数连续段，还需先判无解 |
| 1552. 两球之间的磁力 | 中等 | 最大化最小间距，判定用贪心放球，收缩方向与本题相反 |
| 69. x 的平方根 | 简单 | 最朴素的二分答案，判定是一次乘法，注意用 long 防止平方溢出 |
| LCR 073. 爱吃香蕉的狒狒 | 中等 | 与 875 同题 |