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;
}
标签:返回,return,gcd,int,long,let,答案,ans,神奇
From: https://www.cnblogs.com/moonfdd/p/17410563.html