0878._Nth_Magical_Number.md

878. Nth Magical Number

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/nth-magical-number

内容描述

A positive integer is magical if it is divisible by either A or B.

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 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000

解题方案

思路 1 - 时间复杂度: O(log(AB))- 空间复杂度: O(N)*****

• 从数据范围看来，N高达10^9，直接遍历不现实
• 注意到魔法数是有循环的，我们令P=A和B的最小公倍数，那么在每P个数中，魔法数的数量和位置都是相同的，因此我们只需要计算1-P中间的魔法数
• 1P的魔法数数量是 P/A+P/B-1，注意到，P是A和B的最小公倍数，因此1P中，既能被A整除，也能被B整除，只有一个数，就是P
• 现在问题变成，在1~P中，求第n个魔法数
• 解法一：A和B的数据范围只有40000，因此，1~P中魔法数，不超过80000个，只需要把所有的魔法数求出来，排个序，就能求出第n个魔法数，复杂度是O(A+B)
• 解法二：注意到，我们在1p中任取一个数x（x<p），1x中魔法数的数量是x/A+x/B，注意这个是整除。因此我们可以对1~p进行二分，就能求出第n个魔法数，复杂度是O(log(A*B))

class Solution {
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    private int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    public static int MOD = 1000000007;

    private int find(int a, int b, int n) {
        int left = 1, right = lcm(a, b);

        while (right - left > 1) {
            int mid = (left + right) / 2;
            if (mid / a + mid / b >= n) {
                right = mid;
            } else {
                left = mid;
            }
        }

        return right;
    }

    public int nthMagicalNumber(int N, int A, int B) {
        int repeat = lcm(A, B);
        int num = repeat / A + repeat / B - 1;

        int ret = find(A, B, (N - 1) % num + 1);
        ret += (long)((N - 1) / num) * repeat % MOD;
        if (ret > MOD) {
            ret -= MOD;
        }
        return ret;
    }
}