Skip to content

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中间的魔法数
  • 1~P的魔法数数量是 P/A+P/B-1,注意到,P是A和B的最小公倍数,因此1~P中,既能被A整除,也能被B整除,只有一个数,就是P
  • 现在问题变成,在1~P中,求第n个魔法数
  • 解法一:A和B的数据范围只有40000,因此,1~P中魔法数,不超过80000个,只需要把所有的魔法数求出来,排个序,就能求出第n个魔法数,复杂度是O(A+B)
  • 解法二:注意到,我们在1~p中任取一个数x(x<p),1~x中魔法数的数量是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;
    }
}


回到顶部