共计 2436 个字符，预计需要花费 7 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 878. 第 N 个神奇数字 ，难度为 艰难。
Tag :「数学」、「容斥原理」、「二分」、「gcd」、「lcm」
一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 $10^9 + 7$ 取模 后的值。
示例 1：
输出：n = 1, a = 2, b = 3
输入：2示例 2：
输出：n = 4, a = 2, b = 3
输入：6提醒：
- $1 <= n <= 10^9$
- $2 <= a, b <= 4 \times 10^4$
数学
提醒一 : 从题面剖析常见做法，从常见做法复杂度登程思考其余做法
若不看数据范畴，只看题面，容易想到的做法是「多路归并」：起始应用两个指针指向 [a, 2a, 3a, ...] 和 [b, 2b, 3b, ...] 的结尾，一直比拟两指针所指向的数值大小，从而决定将谁后移，并不断更新顺位计数。
该做法常见，但其复杂度为 $O(n)$，对于本题 $n = 1e9$ 来说并不可行。
确定线性复杂度的做法不可行后，咱们思考是否存在对数复杂度的做法。
提醒二 : 如何思考常见的对数复杂度做法，如何定义二段性
题目要咱们求第 $n$ 个符合要求的数，假如咱们想要通过「二分」来找该数值，那么咱们须要剖析其是否存在「二段性」。
假如在所有「可能被 a 或 b 整除的数」造成的数轴上，咱们要找的宰割点是 k，咱们冀望通过「二分」来找到 k 值，那么须要定义某种性质，使得 k 右边的数均满足该性质，k 左边的数均不满足该性质。
不难想到可依据题意来设定该性质：小于 k 的任意数字 x 满足在 $[0, x]$ 范畴数的个数有余 k 个，而大于等于 k 的任意数字 x 则不满足该性质。
提醒三 : 如何实现高效的 check 函数
当确定应用「二分」来做时，剩下问题转化为：如何疾速得悉某个 $[0, n]$ 中满足要求的数的个数。
容易联想到「容斥原理」：能被 a 或 b 整除的数的个数 = 可能被 a 整除的数的个数 + 可能被 b 整除的数的个数 – 既能被 a 又能被 b 整除的数的个数。
$$
\left \lfloor \frac{n}{a} \right \rfloor + \left \lfloor \frac{n}{b} \right \rfloor – \left \lfloor \frac{n}{c} \right \rfloor
$$
其中 c 为 a 和 b 的最小公倍数。
求解最小公倍数 lcm 须要实现最大公约数 gcd，两者模板别离为：
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {return a * b / gcd(a, b);
}提醒四 : 如何确定值域
一个合格的值域只须要确定答案在值域范畴即可，因而咱们能够间接定值域大小为 $1e20$。
或是依据 a 和 b 的取值来大抵确定：假如两者中的较大值为 $m$，此时第 $n$ 个符合要求的数最大不会超过 $n \times m$，因而也能够设定值域大小为 $[0, 40000n]$。
Java 代码：
class Solution {
int n, a, b, c;
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}
public int nthMagicalNumber(int _n, int _a, int _b) {n = _n; a = _a; b = _b; c = a * b / gcd(a, b);
long l = 0, r = (long)1e20;
while (l < r) {
long mid = l + r >> 1;
if (check(mid) >= n) r = mid;
else l = mid + 1;
}
return (int)(r % 1000000007);
}
long check(long x) {return x / a + x / b - x / c;}
}TypeScript 代码：
function nthMagicalNumber(n: number, a: number, b: number): number {function gcd(a: number, b: number): number {return b == 0 ? a : gcd(b, a % b)
}
function check(x: number): number {return Math.floor(x / a) + Math.floor(x / b) - Math.floor(x / c)
}
const c = Math.floor(a * b / gcd(a, b))
let l = 0, r = 1e19
while (l < r) {const mid = Math.floor((l + r) / 2)
if (check(mid) >= n) r = mid
else l = mid + 1
}
return r % 1000000007
}Python3 代码：
class Solution:
def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
def check(x):
return x // a + x // b - x // c
c = a * b // gcd(a, b)
l, r = 0, 1e20
while l < r:
mid = (l + r) // 2
if check(mid) >= n:
r = mid
else:
l = mid + 1
return int(r % 1000000007)- 工夫复杂度：$O(\log{N})$，其中 $N = 1e20$ 为值域大小
- 空间复杂度：$O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.878 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
