878-第 N 个神奇数字(Nth Magical Number)
发表于：2021-12-03 | 分类： 困难
字数统计: 1.5k | 阅读时长: 8分钟 | 阅读量：

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

英文原文

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

Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 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

 

Constraints:

  • 1 <= n <= 109
  • 2 <= a, b <= 4 * 104

中文题目

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

 

提示：

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

通过代码

官方题解

方法一：数学方法

思路和算法

用数学方法找出第 $N$ 个神奇数字。

神奇数字是有规律。设 $L$ 为 $A$，$B$ 的最小公倍数，如果 $X \leq L$ 是神奇数字，那么 $X + L$ 也是神奇数字，因为 $A | X$， $A | L$ 可以推出 $A | (X + L)$，对于 $B$ 也是如此。

有 $M = \frac{L}{A} + \frac{L}{B} - 1$ 个神奇数字小于等于 $L$： 其中 $\frac{L}{A}$ 个是能被 $A$ 整除的，$\frac{L}{B}$ 个能被 $B$ 整除，$1$ 个能同时被 $A，B$ 整除。

设 $N = Mq + r$（$r < M$），前 $Lq$ 个数字有 $Mq$ 个神奇数字，$(Lq + 1, Lq + 2, \cdots)$ 之间有 $r$ 个神奇数字。可以暴力搜 $r$，下一个神奇数字要么是 $Lq + A$ 要么是 $L*q + B$，依此类推。

[solution1-Java]
class Solution {
    public int nthMagicalNumber(int N, int A, int B) {
        int MOD = 1_000_000_007;
        int L = A / gcd(A, B) * B;
        int M = L / A + L / B - 1;
        int q = N / M, r = N % M;

        long ans = (long) q * L % MOD;
        if (r == 0)
            return (int) ans;

        int[] heads = new int[]{A, B};
        for (int i = 0; i < r - 1; ++i) {
            if (heads[0] <= heads[1])
                heads[0] += A;
            else
                heads[1] += B;
        }

        ans += Math.min(heads[0], heads[1]);
        return (int) (ans % MOD);
    }

    public int gcd(int x, int y) {
        if (x == 0) return y;
        return gcd(y % x, x);
    }
}
[solution1-Python]
class Solution(object):
    def nthMagicalNumber(self, N, A, B):
        from fractions import gcd
        MOD = 10**9 + 7

        L = A / gcd(A, B) * B
        M = L / A + L / B - 1
        q, r = divmod(N, M)

        if r == 0:
            return q * L % MOD

        heads = [A, B]
        for _ in xrange(r - 1):
            if heads[0] <= heads[1]:
                heads[0] += A
            else:
                heads[1] += B

        return (q * L + min(heads)) % MOD
[solution1-C++]
class Solution {
public:
    int nthMagicalNumber(int N, int A, int B) {
        int MOD = 1e9 + 7;
        int L = A / gcd(A, B) * B;
        int M = L / A + L / B - 1;
        int q = N / M, r = N % M;

        long ans = (long) q * L % MOD;
        if (r == 0)
            return (int) ans;

        int heads[2] = {A, B};
        for (int i = 0; i < r - 1; ++i) {
            if (heads[0] <= heads[1])
                heads[0] += A;
            else
                heads[1] += B;
        }

        ans += min(heads[0], heads[1]);
        return (int) (ans % MOD);
    }

    int gcd(int x, int y) {
        if (x == 0) return y;
        return gcd(y % x, x);
    }
};
[solution1-Javascript]
var nthMagicalNumber = function(N, A, B) {
    gcd = (x, y) => {
        if (x == 0) return y;
        return gcd(y % x, x);
    }

    const MOD = 1000000007;
    const L = A / gcd(A, B) * B;
    const M = L / A + L / B - 1;
    const q = Math.trunc(N / M), r = N % M;

    let ans = q * L % MOD;
    if (r == 0)
        return ans;

    let heads = [A, B];
    for (let i = 0; i < r - 1; ++i) {
        if (heads[0] <= heads[1])
            heads[0] += A;
        else
            heads[1] += B;
    }

    ans += Math.min(heads[0], heads[1]);
    return ans % MOD;
};

复杂度分析

  • 时间复杂度： $O(A + B)$，数学计算复杂度为 $O(1)$，计算 $q*M$ 后的 $r$ 个神奇数字的复杂度为 $O(M)$，即 $O(A+B)$。

  • 空间复杂度： $O(1)$。

方法二： 二分搜索

思路

小于等于 $x$ 的神奇数字的个数是一个单调递增函数，可以用二分搜索来做这道题。

算法

设 $L = lcm(A, B)$，为 $A$，$B$ 的 最小公倍数，$L = \frac{A * B}{gcd(A, B)}$。

$f(x)$ 为小于等于 $x$ 的神奇数字的个数。$f(x) = \lfloor \frac{x}{A} \rfloor + \lfloor \frac{x}{B} \rfloor - \lfloor \frac{x}{L} \rfloor$。有 $\lfloor \frac{x}{A} \rfloor$ 个数字能被 $A$ 整除的，$\lfloor \frac{x}{B} \rfloor$ 个数字能被 $B$ 整除，同时需要减去 $\lfloor \frac{x}{L} \rfloor$ 个能被 $A$，$B$ 整除的数。

[solution2-Java]
class Solution {
    public int nthMagicalNumber(int N, int A, int B) {
        int MOD = 1_000_000_007;
        int L = A / gcd(A, B) * B;

        long lo = 0;
        long hi = (long) 1e15;
        while (lo < hi) {
            long mi = lo + (hi - lo) / 2;
            // If there are not enough magic numbers below mi...
            if (mi / A + mi / B - mi / L < N)
                lo = mi + 1;
            else
                hi = mi;
        }

        return (int) (lo % MOD);
    }

    public int gcd(int x, int y) {
        if (x == 0) return y;
        return gcd(y % x, x);
    }
}
[solution2-Python]
class Solution(object):
    def nthMagicalNumber(self, N, A, B):
        from fractions import gcd
        MOD = 10**9 + 7
        L = A / gcd(A,B) * B

        def magic_below_x(x):
            #How many magical numbers are <= x?
            return x / A + x / B - x / L

        lo = 0
        hi = 10**15
        while lo < hi:
            mi = (lo + hi) / 2
            if magic_below_x(mi) < N:
                lo = mi + 1
            else:
                hi = mi

        return lo % MOD
[solution2-C++]
class Solution {
public:
    int nthMagicalNumber(int N, int A, int B) {
        int MOD = 1e9 + 7;
        int L = A / gcd(A, B) * B;

        long lo = 0;
        long hi = (long) 1e15;
        while (lo < hi) {
            long mi = lo + (hi - lo) / 2;
            // If there are not enough magic numbers below mi...
            if (mi / A + mi / B - mi / L < N)
                lo = mi + 1;
            else
                hi = mi;
        }

        return (int) (lo % MOD);
    }

    int gcd(int x, int y) {
        if (x == 0) return y;
        return gcd(y % x, x);
    }
};
[solution2-Javascript]
var nthMagicalNumber = function(N, A, B) {
    gcd = (x, y) => {
        if (x == 0) return y;
        return gcd(y % x, x);
    }

    const MOD = 1000000007;
    const L = A / gcd(A, B) * B;

    let lo = 0;
    let hi = 1e15;
    while (lo < hi) {
        let mi = lo + Math.trunc((hi - lo) / 2);
        // If there are not enough magic numbers below mi...
        if (Math.trunc(mi/A) + Math.trunc(mi/B) - Math.trunc(mi/L) < N)
            lo = mi + 1;
        else
            hi = mi;
    }

    return lo % MOD;
};

复杂度分析

  • 时间复杂度： $O(\log(N * \max(A, B)))$。

  • 空间复杂度： $O(1)$。

统计信息

通过次数 提交次数 AC比率
4555 16131 28.2%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
二分查找 数学
上一篇:
877-石子游戏(Stone Game)
下一篇:
879-盈利计划(Profitable Schemes)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo