一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字。
因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。
输入：n = 4, a = 2, b = 3。
输出：6。
过程描述：
1.计算 a 和 b 的最小公倍数 lcm。
2.初始化变量 l 为0，变量 r 为 (n * min(a, b))，其中 min(a, b) 表示 a 和 b 中的最小值。在这个范围内通过二分查找获得第 n 个神奇数字。
3.对于每个二分查找猜测值，计算在 a和b中出现的神奇数字个数：m/a + m/b。然后计算 a 和 b 的公共倍数 lcm 在 m 范围内出现的神奇数字个数：m/lcm。
4.如果出现的神奇数字总数大于或等于 n，则将当前猜测值存储在变量 ans 中，并将右边界向左移动一位（即缩小区间的范围）。
5.如果出现的神奇数字总数小于 n，则将左边界向右移动一位（即扩大区间的范围），并继续迭代。
6.二分查找过程结束后，返回答案 ans % (10^9 + 7)。
时间复杂度为 O(logN)，空间复杂度为 O(1)。
在这个算法中，使用了二分查找来搜索第 n 个神奇数字。在最坏情况下，二分查找的迭代次数为 O(logN)。因此，时间复杂度为 O(logN)。
另外，在算法中只使用了几个整数变量来存储值和计算结果，所以空间复杂度为 O(1)。
go完整代码如下：
package main
func nthMagicalNumber(n int, a int, b int) int {
// 求a和b的最小公倍数
lcm := int64(a / gcd(a, b) * b)
var ans int64 = 0
// l = 0
// r = (long) n * Math.min(a, b)
l, r := int64(0), int64(n)*int64(min(a, b))
for l <= r {
m := (l + r) / 2
if m/int64(a)+m/int64(b)-m/lcm >= int64(n) {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return int(ans % 1000000007)
}
func gcd(a int, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
func main() {
n := 1000000000
a := 40000
b := 40000
result := nthMagicalNumber(n, a, b)
println(result)
}
rust完整代码如下：
fn nth_magical_number(n: i32, a: i32, b: i32) -> i32 {
let n = n as i64;
let a = a as i64;
let b = b as i64;
// 求a和b的最小公倍数
let lcm = a / gcd(a, b) * b;
let mut ans = 0;
// l = 0
// r = (long) n * Math.min(a, b)
let mut l = 0;
let mut r = (n * std::cmp::min(a, b));
while l <= r {
let m = (l as i64 + r as i64) / 2;
if m / a as i64 + m / b as i64 - m / lcm as i64 >= n as i64 {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
(ans % 1000000007) as i32
}
fn gcd(a: i64, b: i64) -> i64 {
if b == 0 {
a
} else {
gcd(b, a % b)
}
}
fn main() {
let n = 1000000000;
let a = 40000;
let b = 40000;
let result = nth_magical_number(n, a, b);
println!("{}", result);
}
c语言完整代码如下：
#include <stdio.h>
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
int nthMagicalNumber(int n, int a, int b) {
// 求a和b的最小公倍数
long long lcm = (long long)a / gcd(a, b) * b;
long long ans = 0;
// l = 0
// r = (long) n * Math.min(a, b)
for (long long l = 0, r = (long long)n * (a < b ? a : b), m = 0; l <= r;) {
m = (l + r) / 2;
if (m / a + m / b - m / lcm >= n) {
ans = m;
r = m - 1;
}
else {
l = m + 1;
}
}
return (int)(ans % 1000000007);
}
int main() {
int n = 1000000000;
int a = 40000;
int b = 40000;
int result = nthMagicalNumber(n, a, b);
printf("%d\n", result);
return 0;
}
c++完整代码如下：
#include <iostream>
using namespace std;
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
int nthMagicalNumber(int n, int a, int b) {
// 求a和b的最小公倍数
long long lcm = (long long)a / gcd(a, b) * b;
long long ans = 0;
// l = 0
// r = (long) n * Math.min(a, b)
for (long long l = 0, r = (long long)n * min(a, b), m = 0; l <= r;) {
m = (l + r) / 2;
if (m / a + m / b - m / lcm >= n) {
ans = m;
r = m - 1;
}
else {
l = m + 1;
}
}
return (int)(ans % 1000000007);
}
int main() {
int n = 1000000000;
int a = 40000;
int b = 40000;
int result = nthMagicalNumber(n, a, b);
cout << result << endl;
return 0;
}
