leetcode [878] 第 N 个神奇数字

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

如果正整数可以被 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 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000

来自题解：

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

神奇数字是有规律。设 L 为 A，B 的最小公倍数，如果 X ≤ L 是神奇数字，那么 X+L 也是神奇数字。

有 M = L / A + L / B − 1个神奇数字小于等于 L： 其中 L / A​ 个是能被 A 整除的，L / B 个能被 B 整除，1 个能同时被 A，B整除。

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

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        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 range(r - 1):
            if heads[0] <= heads[1]:
                heads[0] += A
            else:
                heads[1] += B

        return (q * L + min(heads)) % MOD