【2022-11-22每日一题】878. 第 N 个神奇数字[Hard]

2022-11-22每日一题：878. 第 N 个神奇数字

难度：Hard

标签：数学 、 二分查找

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。

示例 1：

输入：n = 1, a = 2, b = 3
输出：2

示例 2：

输入：n = 4, a = 2, b = 3
输出：6

提示：

• 1 <= n <= 109
• 2 <= a, b <= 4 * 104

方法一：数学+二分查找

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

const mod int = 1e9+7
// 系统库二分查找
func nthMagicalNumber(n int, a int, b int) int {
    c := a * b / gcd(a, b) // a,b最少公倍数
    r := (a + b) * n
    return sort.Search(r, func(x int) bool {
        return x/a+x/b-x/c >= n
    }) % mod
}

// 手写二分查找1
func nthMagicalNumber(n int, a int, b int) int {
    lcm := a / gcd(a, b) * b
    left, right := min(a, b), min(a, b)*n // 开区间 (left, right)
    for left+1 < right { // 开区间不为空
        mid := left + (right-left)/2
        if mid/a+mid/b-mid/lcm >= n {
            right = mid // 范围缩小到 (left, mid)
        } else {
            left = mid // 范围缩小到 (mid, right)
        }
    }
    return right % (1e9 + 7)
}

// 手写二分查找2
func nthMagicalNumber(n int, a int, b int) int {
    l := min(a, b)
    r := n * min(a, b)
    c := a / gcd(a, b) * b
    for l <= r {
        mid := (l + r) / 2
        cnt := mid/a + mid/b - mid/c
        if cnt >= n {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return (r + 1) % mod
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

// gcd 迭代
func gcd(a, b int) int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

复杂度分析

• 时间复杂度：O(log⁡(n×max⁡(a,b)))，其中 n，b，c 为题目给定的数字。

• 空间复杂度：O(1)，仅使用常量空间开销。

LeetCode题库地址

• https://leetcode.cn/problems/nth-magical-number