878.第 N 个神奇数字

【LetMeFly】878.第 N 个神奇数字

力扣题目链接：https://leetcode.cn/problems/nth-magical-number/

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

 

方法一：二分查找

根据鸽巢原理，在$1\sim x$中，有$\lfloor\frac{x}{a}\rfloor+\lfloor\frac{x}{b}\rfloor-\lfloor\frac{x}{c}\rfloor$个“神奇数”，其中$c$是$a$和$b$的最小公倍数。

因此，我们可以直接二分$x$找到第$n$个“神奇数”即可。

• 时间复杂度$O(\log(n\times\min(a, b)))$
• 空间复杂度$O(1)$

AC代码

C++

typedef long long ll;
class Solution {
public:
    int nthMagicalNumber(int n, ll a, ll b) {
        ll c = lcm(a, b);
        ll l = min(a, b), r = n * min(a, b);
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (mid / a + mid / b - mid / c >= n)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return (r + 1) % 1000000007;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127978493