题目描述

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

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

样例

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

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

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

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

注意

• 1 <= N <= 10^9
• 2 <= A <= 40000
• 2 <= B <= 40000

算法

(数学) $O(\log(\max(A, B)) + (A + B) / gcd(A, B))$

1. 不妨假设 $A < B$，如果 $B % A == 0$，则最终答案为 $N * A$。
2. 否则，求 $A$ 和 $B$ 的最小公倍数记为 lcm，再求出 $nA = lcm / A$，$nB = lcm / B$。每增长一个 lcm，就可以走过 $nA + nB - 1$ 这么多数字。
3. 用 $N / (nA + nB - 1)$，即可得到有多少个整的 lcm。
4. 之后 $N = N % (nA + nB - 1)$，至此剩余的部分可以暴力枚举。记 $t1 = (N / (nA + nB - 1)) * lcm / A$，$t2 = (N / (nA + nB - 1)) * lcm / B$，然后每次往后走的时候比较 $(t1 + 1) * A$ 和 $(t2 + 1) * B$，然后决定下一个多少。

时间复杂度

• 求 gcd 的时间为 $O(\log(\max(A, B))$。由于最后会将 N 减少到(A + B) / gcd(A, B)，故只需要再枚举这么多数字即可，故时间复杂度为 $O(\log(\max(A, B)) + (A + B) / gcd(A, B))$。

C++ 代码

class Solution {
public:
    #define LL long long
    int gcd(int x, int y) {
        return y ? gcd(y, x % y) : x;
    }

    int nthMagicalNumber(int N, int A, int B) {
        const int mod = 1000000007;
        if (A > B)
            swap(A, B);
        if (B % A == 0)
            return (LL)(N) * A % mod;
        int lcm = A * B / gcd(A, B);

        int nA = lcm / A, nB = lcm / B;

        LL ans = (LL)(N / (nA + nB - 1)) * lcm;
        N %= nA + nB - 1;

        LL t1 = ans / A, t2 = ans / B;
        for (int i = 1; i <= N; i++) {
            if ((t1 + 1) * A < (t2 + 1) * B) {
                t1++;
                ans = t1 * A;
            }
            else if ((t1 + 1) * A > (t2 + 1) * B) {
                t2++;
                ans = t2 * B;
            }
            else {
                t1++;
                t2++;
                ans = t1 * A;
            }
        }
        return ans % mod;
    }
};