878. Nth Magical Number
难度: Hard
刷题内容
原题连接
- https://leetcode.com/problems/nth-magical-number
内容描述
A positive integer is magical if it is divisible by either A or B.
Return the N-th magical number. Since the answer may be very large, return it modulo 10^9 + 7.
Example 1:
Input: N = 1, A = 2, B = 3
Output: 2
Example 2:
Input: N = 4, A = 2, B = 3
Output: 6
Example 3:
Input: N = 5, A = 2, B = 4
Output: 10
Example 4:
Input: N = 3, A = 6, B = 4
Output: 8
Note:
1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000
解题方案
思路 1 *- 时间复杂度: O(log(AB))*- 空间复杂度: O(N)***
- 从数据范围看来，N高达10^9，直接遍历不现实
- 注意到魔法数是有循环的，我们令P=A和B的最小公倍数，那么在每P个数中，魔法数的数量和位置都是相同的，因此我们只需要计算1-P中间的魔法数
- 1~P的魔法数数量是 P/A+P/B-1，注意到，P是A和B的最小公倍数，因此1~P中，既能被A整除，也能被B整除，只有一个数，就是P
- 现在问题变成，在1~P中，求第n个魔法数
- 解法一：A和B的数据范围只有40000，因此，1~P中魔法数，不超过80000个，只需要把所有的魔法数求出来，排个序，就能求出第n个魔法数，复杂度是O(A+B)
- 解法二：注意到，我们在1~p中任取一个数x（x<p），1~x中魔法数的数量是x/A+x/B，注意这个是整除。因此我们可以对1~p进行二分，就能求出第n个魔法数，复杂度是O(log(A*B))
class Solution {
private int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
private int lcm(int a, int b) {
return a * b / gcd(a, b);
}
public static int MOD = 1000000007;
private int find(int a, int b, int n) {
int left = 1, right = lcm(a, b);
while (right - left > 1) {
int mid = (left + right) / 2;
if (mid / a + mid / b >= n) {
right = mid;
} else {
left = mid;
}
}
return right;
}
public int nthMagicalNumber(int N, int A, int B) {
int repeat = lcm(A, B);
int num = repeat / A + repeat / B - 1;
int ret = find(A, B, (N - 1) % num + 1);
ret += (long)((N - 1) / num) * repeat % MOD;
if (ret > MOD) {
ret -= MOD;
}
return ret;
}
}
