2023-05-17：一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字。
因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。
输入：n = 4, a = 2, b = 3。
输出：6。
答案 2023-05-17：
过程描述：
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;}
复制代码
评论