【878. 第 N 个神奇数字】

来源：力扣（LeetCode）
描述：

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 10⁹
• 2 <= a, b <= 4 * 10⁴

方法一：容斥原理 + 二分查找

思路与算法

  题目给出三个数字 n，a，b，满足 1 ≤ n ≤ 10⁹ ， 2 ≤ a, b ≤ 4 × 10⁴ ，并给出「神奇数字」的定义：若一个正整数能被 a 和 b 整除，那么它就是「神奇」的。现在需要求出对于给定 a 和 b 的第 n 个「神奇数字」。设 f(x) 表示为小于等于 x 的「神奇数字」个数，因为小于等于 x 中能被 a 整除的数的个数为 ⌊ x/a ⌋，小于等于 x 中能被 b 整除的个数为 ⌊ x/b ⌋，小于等于 x 中同时能被 a 和 b 整除的个数为 ⌊ x/c ⌋，其中 c 为 a 和 b 的最小公倍数，所以 f(x) 的表达式为：

即f(x) 是一个随着 x 递增单调不减函数。那么我们可以通过「二分查找」来进行查找第 n 个「神奇数字」。

代码：

class Solution {
public:
    const int MOD = 1e9 + 7;
    int nthMagicalNumber(int n, int a, int b) {
        long long l = min(a, b);
        long long r = (long long) n * min(a, b);
        int c = lcm(a, b);
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long cnt = mid / a + mid / b - mid / c;
            if (cnt >= n) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return (r + 1) % MOD;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度分析
时间复杂度： O(log(n × max(a, b)))，其中 n，b，c 为题目给定的数字。
空间复杂度：O(1)，仅使用常量空间开销。

方法二：找规律

思路与算法

  通过「方法一」我们也可以知道小于等于 x × c 的「神奇数字」个数 f(x × c) = q × f© = x × ( c/a + c/b − 1) 个，其中 c 为 a 和 b 的最小公倍数，x 为非负整数。令 m = f©，n = q * m + r，其中 0 ≤ r < m，q 为非负整数。因为不大于 c×q 的「神奇数字」个数为 q * m ，所以我们只需要从 c×q 往后搜第 r 个「神奇数字」即可。又因为对于 c×q 的之后的「神奇数字」只能是 c × q + a, c × q + 2 × a, ⋯ 和 c × q + b, c × q + 2 × b, ⋯ ，那么我们从小到大来搜索到第 r 个「神奇数字」即可。

代码：

class Solution {
public:
    const int MOD = 1e9 + 7;
    int nthMagicalNumber(int n, int a, int b) {
        int c = lcm(a, b);
        int m = c / a + c / b - 1;
        int r = n % m;
        int res = (long long) c * (n / m) % MOD;
        if (r == 0) {
            return res;
        }
        int addA = a, addB = b;
        for (int i = 0; i <  r - 1; ++i) {
            if (addA < addB) {
                addA += a;
            } else {
                addB += b;
            }
        }
        return (res + min(addA, addB) % MOD) % MOD;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析
时间复杂度： O(a+b)，其中 n，b，c 为题目给定的数字。
空间复杂度： O(1)，仅使用常量空间开销。
author：LeetCode-Solution