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

布满荆棘的人生 2023-10-07 21:23 4阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

来源：力扣（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][1201._ III]这题十分类似，相比之下，本题要求正整数只是能被 a 或 b 整除，缺少了一个 c，但是解题思路基本上一模一样，此处便不再赘述。

思路[该 LeetCode 用户题解][LeetCode]。

相关题目：  
[LeetCode\_因式分解\_简单\_263.丑数][LeetCode_263.]  
[LeetCode\_动态规划\_中等\_264.丑数 II][LeetCode_264._ II]  
[LeetCode\_动态规划\_中等\_313.超级丑数][LeetCode_313.]  
[LeetCode\_容斥原理\_二分搜索\_中等\_1201.丑数 III][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;
        }
    }

//思路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);
        }
    }

[1201._ III]: https://blog.csdn.net/weixin_43004044/article/details/129331211
[LeetCode]: https://leetcode.cn/problems/nth-magical-number/solution/er-fen-da-an-rong-chi-yuan-li-by-endless-9j34/
[LeetCode_263.]: https://blog.csdn.net/weixin_43004044/article/details/125957089
[LeetCode_264._ II]: https://blog.csdn.net/weixin_43004044/article/details/125969827
[LeetCode_313.]: https://blog.csdn.net/weixin_43004044/article/details/126074560