题目描述
leetcode 困难题
一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。
示例1：
1
2
| 输入：n = 1, a = 2, b = 3
输出：2
|
示例2:
1
2
| 输入：n = 4, a = 2, b = 3
输出：6
|
提示1：
1
2
| 1 <= n <= 10^9
2 <= a, b <= 4 * 10^4
|
容斥原理 + 二分查找
这道题容易想到的做法是多指针，两个指针分别指向 $a$ 和 $b$ 的某个倍数，并通过不断比较找到第 $n$ 个数，该做法的时间复杂度为 $O(N)$，在该题的数据规模下显然会 TLE。
容易想到的优化方法是通过二分查找找到第 $n$ 个数，但是需要解决的问题是如何确定某个数 $i$ 前面的神奇数字的数量，将该数量设为 $x$。
可以发现每个神奇数字必然满足以下三种情况之一：
- 为 $a$ 的倍数
- 为 $b$ 的倍数
- 为 $lcm(a, b)$ 的倍数
显然通过容斥原理可以得出：
$x$ = $i$ 前面的数为 $a$ 的倍数的数量 + $i$ 前面的数为 $b$ 的倍数的数量 - $i$ 前面的数为 $lcm(a, b)$ 的倍数的数量
也就是
$x = \lfloor \frac{i}{a} \rfloor + \lfloor \frac{i}{b} \rfloor - \lfloor \frac{i}{lcm} \rfloor$
答案为二分查找的左边界，也就是第一个满足的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
private static final int MOD = (int)(1e9 + 7);
private int a;
private int b;
private long lcm;
public int nthMagicalNumber(int n, int a, int b) {
long l = Math.min(a, b);
long r = Long.MAX_VALUE;
this.a = a;
this.b = b;
this.lcm = lcm(a, b);
while(l < r){
long mid = l + (r - l >> 1);
if(get(mid) < n){
l = mid + 1;
}else{
r = mid;
}
}
return (int) (l % MOD);
}
private long get(long mid){
return (mid / a) + (mid / b) - (mid / lcm);
}
private long lcm(int a, int b){
return (a * b) / gcd(a, b);
}
private int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
}
|
类似的，也可以转化成
$x = \lceil \frac{i}{a} \rceil + \lceil \frac{i}{b} \rceil - \lceil \frac{i}{lcm} \rceil$
此时答案为右边界，也就是最后一个满足的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
private static final int MOD = (int)(1e9 + 7);
private int a;
private int b;
private long lcm;
public int nthMagicalNumber(int n, int a, int b) {
long l = Math.min(a, b);
long r = Long.MAX_VALUE;
this.a = a;
this.b = b;
this.lcm = lcm(a, b);
while(l < r){
long mid = l + (r - l >> 1);
if(get(mid) > n){
r = mid;
}else{
l = mid + 1;
}
}
return (int) ((l - 1) % MOD);
}
private long get(long mid){
double temp = mid;
return (long)(Math.ceil(temp / a) + Math.ceil(temp / b) - Math.ceil(temp / lcm));
}
private long lcm(int a, int b){
return (a * b) / gcd(a, b);
}
private int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
}
|