2023-05-17：一个正整数如果能被 a 或 b 整除，那么它是神奇的。 给定三个整数 n , a , b ，返回第 n 个神奇的数字。 因为答案可能很大，所以返回答案 对 10^9 + 7 取模

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

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

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

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