> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/878-nth-magical-number.md).

# 878     Nth Magical Number

## 878. [Nth Magical Number](https://leetcode.com/problems/nth-magical-number/description/)

## 1. Question

A positive integer is*magical* if it is divisible by eitherA orB.

Return the N-th magical number. Since the answer may be very large, **return it modulo**`10^9 + 7.`

**Example 1:**

```
Input: N = 1, A = 2, B = 3
Output: 2
```

**Example 2:**

```
Input: N = 4, A = 2, B = 3
Output: 6
```

**Example 3:**

```
Input: N = 5, A = 2, B = 4
Output: 10
```

**Example 4:**

```
Input: N = 3, A = 6, B = 4
Output: 8
```

**Note:**

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

## 2. Implementation

**(1) Binary Search**

思路：

要找出第N个数能被A或B除，我们可以用二分查找在\[Math.min(A, B), Long.MAX\_VALUE]的范围内找到。在二分查找的过程中，我们先判断如果target number是mid, 它有多少个magic number。如果magic number的数量小于N, 说明mid太小，则将范围缩小到\[mid + 1, end]， 否则mid太大，范围变为\[start, mid]。找magic number的个数，我们可以通过公式 x / A + x / B - x / (A \* B /gcd)得到，其中A \* B /gcd是A, B是最小公倍数， 减去x / (A \* B /gcd)是为了避免计算重复的数字

```java
class Solution {
    public int nthMagicalNumber(int N, int A, int B) {
        long start = Math.min(A, B);
        long end = Long.MAX_VALUE;
        long mod = (long)1e9 + 7;
        int gcd = getGCD(A, B);

        while (start + 1 < end) {
            long mid = start + (end - start) / 2;

            if (!isValid(A, B, N, gcd, mid)) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }

        return isValid(A, B, N, gcd, start) ? (int)(start % mod) : (int)(end % mod);
    }

    public int getGCD(int a, int b) {
        while (b > 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

    public boolean isValid(int a, int b, int n, int gcd, long target) {
        return target / a + target / b - target / ((a * b) / gcd) >= n;
    }
}
```

## 3. Time & Space Complexity

**Binary Search:** 时间复杂度O(log(Max)), max表示的是Log.MAX\_VALUE, 空间复杂度O(1)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/878-nth-magical-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.