LeetCode-878-第N个神奇数字

1、二分查找

如果我们用函数$f(x)$表示数字小于x的神奇数字的个数，显然我们可以得到如下的公式：$f(x)=\lfloor \frac{x}{a}\rfloor +\lfloor \frac{x}{b}\rfloor -\lfloor \frac{x}{c}\rfloor$，其中c为a和b的最小公倍数。因此我们可以在$[a,a^n]$的区间中进行二分查找并计算当前的$f(x)$的值并与目标值进行比较，最终返回具体的值。

class Solution {
public:
    const int MOD = 1e9 + 7;
    int nthMagicalNumber(int n, int a, int b) {
        long long l = min(a, b);
        long long r = (long long) n * min(a, b);
        int c = lcm(a, b);// a和b的最小公倍数
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long cnt = mid / a + mid / b - mid / c;
            if (cnt >= n) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return (r + 1) % MOD;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2、数学优化

我们可以利用最小公倍数c来缩小n的范围。我们可以计算出$f(c)$的个数为$c/a+c/b-1$，因此我们可以化简为$f(x)=q\ast f(c)+m$，因此我们只需要在此基础上查找其后m个神奇数字即可。

class Solution {
public:
    const int MOD = 1e9 + 7;
    int nthMagicalNumber(int n, int a, int b) {
        int c = lcm(a, b);
        int m = c / a + c / b - 1;
        int r = n % m;
        int res = (long long) c * (n / m) % MOD;
        if (r == 0) {
            return res;
        }
        int addA = a, addB = b;
        for (int i = 0; i <  r - 1; ++i) {
            if (addA < addB) {
                addA += a;
            } else {
                addB += b;
            }
        }
        return (res + min(addA, addB) % MOD) % MOD;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22