LeetCode878-第N个神奇数字

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/nth-magical-number/

中文链接：https://leetcode-cn.com/problems/nth-magical-number/

题目详述

如果正整数可以被 A 或 B 整除，那么它是神奇的。

返回第 N 个神奇数字。由于答案可能非常大，返回它模 10^9 + 7 的结果。

示例 1：

1
2
输入：N = 1, A = 2, B = 3
输出：2

示例 2：

1
2
输入：N = 4, A = 2, B = 3
输出：6

示例 3：

1
2
输入：N = 5, A = 2, B = 4
输出：10

示例 4：

1
2
输入：N = 3, A = 6, B = 4
输出：8

提示：

  1. 1 <= N <= 10^9
  2. 2 <= A <= 40000
  3. 2 <= B <= 40000

题目详解

  • 直接二分结果 i，统计 [1, i] 有多少个数是 A 的倍数或者 B 的倍数。
  • 问题的关键字在于求出这个数目，为 i / A + i / B + i / lcm，其中 lcm 是 A 与 B 的最小公倍数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00878 {

    public int nthMagicalNumber(int N, int A, int B) {
        long l = 1, r = Long.MAX_VALUE;
        int lcm = A * B / gcd(A, B);
        while (l < r) {
            long mid = l + r >>> 1;
            if (mid / A + mid / B - mid / lcm >= N) r = mid;
            else l = mid + 1;
        }
        return (int) (r % 1000000007);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}