Hard

题目描述

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

给定三个整数 n, a, 和 b，返回第 n 个神奇数字。由于答案可能很大，返回它对 10^9 + 7 取模的结果。

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 10^9
  • 2 <= a, b <= 4 * 10^4

解题思路

这道题要求找到第 n 个能被 a 或 b 整除的数字。我们可以用二分搜索来解决这个问题。

核心思路：

  1. 二分搜索范围：最小值是 min(a, b)，最大值可以设为 n * min(a, b)

  2. 计算小于等于 x 的神奇数字个数：使用容斥原理

    • 能被 a 整除的数字个数：x / a
    • 能被 b 整除的数字个数：x / b
    • 能被 a 和 b 同时整除的数字个数：x / lcm(a, b)
    • 总个数 = x/a + x/b - x/lcm(a, b)

  3. 最小公倍数计算：lcm(a, b) = a * b / gcd(a, b)

算法步骤：

  • 使用二分搜索在可能的范围内查找
  • 对于每个中间值 mid，计算小于等于 mid 的神奇数字个数
  • 如果个数 >= n，说明答案在左半部分；否则在右半部分
  • 最终找到第 n 个神奇数字

这种方法避免了直接枚举所有数字，时间复杂度大大降低。

代码实现

class Solution {
public:
    int nthMagicalNumber(int n, int a, int b) {
        const int MOD = 1e9 + 7;
        
        long long lcm = (long long)a * b / __gcd(a, b);
        
        long long left = min(a, b);
        long long right = (long long)n * min(a, b);
        
        while (left < right) {
            long long mid = left + (right - left) / 2;
            long long count = mid / a + mid / b - mid / lcm;
            
            if (count < n) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left % MOD;
    }
};

class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        import math
        
        MOD = 10**9 + 7
        
        lcm = a * b // math.gcd(a, b)
        
        left, right = min(a, b), n * min(a, b)
        
        while left < right:
            mid = (left + right) // 2
            count = mid // a + mid // b - mid // lcm
            
            if count < n:
                left = mid + 1
            else:
                right = mid
        
        return left % MOD

public class Solution {
    public int NthMagicalNumber(int n, int a, int b) {
        const int MOD = 1000000007;
        
        long lcm = (long)a * b / Gcd(a, b);
        
        long left = Math.Min(a, b);
        long right = (long)n * Math.Min(a, b);
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            long count = mid / a + mid / b - mid / lcm;
            
            if (count < n) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return (int)(left % MOD);
    }
    
    private int Gcd(int a, int b) {
        return b == 0 ? a : Gcd(b, a % b);
    }
}

var nthMagicalNumber = function(n, a, b) {
    const MOD = 1000000007;
    
    const gcd = (x, y) => y === 0 ? x : gcd(y, x % y);
    const lcm = (x, y) => x * y / gcd(x, y);
    
    const L = lcm(a, b);
    
    let left = 1, right = n * Math.min(a, b);
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        const count = Math.floor(mid / a) + Math.floor(mid / b) - Math.floor(mid / L);
        
        if (count < n) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log(n * min(a,b)))二分搜索的时间复杂度
空间复杂度O(1)只使用常数额外空间