LC 878. 第 N 个神奇数字

题目描述

这是 LeetCode 上的 878. 第 N 个神奇数字 ,难度为 困难

一个正整数如果能被 ab 整除,那么它是神奇的。

给定三个整数 n , a , b ,返回第 n 个神奇的数字。因为答案可能很大,所以返回答案 对 $10^9 + 7$ 取模 后的值。

示例 1:

1
2
3
输入:n = 1, a = 2, b = 3

输出:2

示例 2:
1
2
3
输入: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$ 个符合要求的数,假设我们想要通过「二分」来找该数值,那么我们需要分析其是否存在「二段性」。

假设在所有「能够被 ab 整除的数」形成的数轴上,我们要找的分割点是 k,我们期望通过「二分」来找到 k 值,那么需要定义某种性质,使得 k 左边的数均满足该性质,k 右边的数均不满足该性质。

不难想到可根据题意来设定该性质:小于 k 的任意数字 x 满足在 $[0, x]$ 范围数的个数不足 k 个,而大于等于 k 的任意数字 x 则不满足该性质。

提示三 : 如何实现高效的 check 函数

当确定使用「二分」来做时,剩下问题转化为:如何快速得知某个 $[0, n]$ 中满足要求的数的个数。

容易联想到「容斥原理」:能被 ab 整除的数的个数 = 能够被 a 整除的数的个数 + 能够被 b 整除的数的个数 - 既能被 a 又能被 b 整除的数的个数

其中 cab 的最小公倍数。

求解最小公倍数 lcm 需要实现最大公约数 gcd,两者模板分别为:

[]
1
2
3
4
5
6
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);
}

提示四 : 如何确定值域

一个合格的值域只需要确定答案在值域范围即可,因此我们可以直接定值域大小为 $1e18$。

或是根据 ab 的取值来大致确定:假设两者中的较大值为 $m$,此时第 $n$ 个符合要求的数最大不会超过 $n \times m$,因此也可以设定值域大小为 $[0, 40000n]$。

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)1e18;
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;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int n, a, b, c;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
long check(long x) {
return x / a + x / b - x / c;
}
int nthMagicalNumber(int _n, int _a, int _b) {
n = _n; a = _a; b = _b; c = a * b / gcd(a, b);
long l = 0, r = 1e18;
while (l < r) {
long mid = l + r >> 1;
if (check(mid) >= n) r = mid;
else l = mid + 1;
}
return (int)(r % 1000000007);
}
};

Python3 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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, 1e18
while l < r:
mid = (l + r) // 2
if check(mid) >= n:
r = mid
else:
l = mid + 1
return int(r % 1000000007)

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 = 1e18
while (l < r) {
const mid = Math.floor((l + r) / 2)
if (check(mid) >= n) r = mid
else l = mid + 1
}
return r % 1000000007
}

  • 时间复杂度:$O(\log{N})$,其中 $N = 1e18$ 为值域大小
  • 空间复杂度:$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.878 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!