0878：第 N 个神奇数字（1896 分）

力扣第 95 场周赛第 3 题

题目

一个正整数如果能被 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

分析

• 典型的二分查找，查找第一个 x，使得 <=x 的神奇数字个数 >=n 即可
• <=x 的神奇数字个数，用容斥定理即可

解答

1
2
3
4
5
6

class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        mod = 10**9+7
        def cal(x):
            return x//a+x//b-x//lcm(a,b)
        return bisect_left(range(a*n),n,key=cal)%mod

0 ms