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;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接