LeetCode_二分搜索_容斥原理_困难_878.第 N 个神奇数字

1.题目

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

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

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

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

提示：
1 <= n <= 10⁹
2 <= a, b <= 4 * 10⁴

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/nth-magical-number

2.思路

（1）暴力穷举法
暴力穷举法比较容易想到，即从正整数 res = 1 开始进行递增枚举，如果 res 能被 a 或 b 整除，那么 n–，直到 n = 0 为止，此时 res 即为第 N 个神奇数字。但是由于 n 的取值范围太大，该方法的时间复杂度较高，所以在 LeetCode 中提交会出现“超出时间限制”的提示！

（2）二分搜索 & 容斥原理
本题与1201.丑数 III这题十分类似，相比之下，本题要求正整数只是能被 a 或 b 整除，缺少了一个 c，但是解题思路基本上一模一样，此处便不再赘述。

思路该 LeetCode 用户题解。

相关题目：
LeetCode_因式分解_简单_263.丑数
LeetCode_动态规划_中等_264.丑数 II
LeetCode_动态规划_中等_313.超级丑数
LeetCode_容斥原理_二分搜索_中等_1201.丑数 III

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        int MOD_NUM = (int) 1e9 + 7;
        int res = 1;
        while (true) {
            if (res % a == 0 || res % b == 0) {
                n--;
                if (n == 0) {
                    break;
                }
            }
            res = (res + 1) % MOD_NUM;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//思路2————二分搜索 & 容斥原理
class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        long MOD_NUM = (long) 1e9 + 7;
        long left = 1;
        long right = (long) Math.min(a, b) * n;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (getCnt(mid, a, b) < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return (int) (left % MOD_NUM);
    }

	//返回 [1, mid] 中能被 a 或 b 整除的数的个数
    public long getCnt(long mid, int a, int b) {
        return mid / a + mid / b - mid / lcm(a, b);
    }

    //返回 a 和 b 的最大公约数 (Greatest Common Divisor, GCD)
    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    //返回 a 和 b 的最小公倍数 (Least Common Multiple, LCM)
    public int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
}
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
32