题目

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

解题思路

二分查找 + 容斥原理

  • 今天这题我缺少了相应的基础知识容斥原理导致我解题到关键部分无法正确解出答案。

首先我们要先将问题转换一下，第N个神奇数字我们把它转化成一共N个神奇数字，那么我们只要求出一共有N个神奇数字即可得到答案。

求一共多少神奇数字 n // a + n // b - n // lcm这样我们就能得到目前一共多少神奇数字了。

二分查找n

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        import math
        MOD = 10 ** 9 + 7

        def gcd(a, b):
            return a if b == 0 else gcd(b, a % b)

        lcm = math.lcm(a, b)
        l, r = 0, min(a, b) * n
        while l + 1 < r:  # (l, r)开区间
            mid = (r - l >> 1) + l
            if (mid // a + mid // b) - mid // lcm >= n:
                r = mid  # 范围缩小到(l, mid)
            else:
                l = mid  # 范围缩小到(mid, r)
        return r % MOD

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int nthMagicalNumber(int n, int a, int b) {
        const long MOD = 1000000000 + 7;
        long c = lcm(a, b);
        long l = 0, r = (long)min(a, b) * n;
        while (l + 1 < r)
        {
            long mid = (r - l >> 1) + l;
            if (mid / a + mid / b - mid / c >= n)
            {
                r = mid;
            }
            else
            {
                l = mid;
            }
        }
        return r % MOD;
    }

    long gcd(long a, long b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    long lcm(long a, long b)
    {
        return (a * b) / gcd(a, b);
    }
};