这个解决方案背后的直觉

Question

我正在尝试解决关于 LeetCode.com 的问题：

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. For e.g., for N = 5, A = 2, B = 4, output is 10.

highly upvoted solution 建议 'searching' 作为答案。但我不明白如何将其建模为搜索问题——这也是一个二进制搜索问题。有人可以指出背后的直觉吗？

int nthMagicalNumber(int N, int A, int B) {
    long lcm = A * B / __gcd(A, B), l = 2, r = 1e14, mod = 1e9 + 7;
    while (l < r) {
        long m = (l + r) / 2;
        if (m / A + m / B - m / lcm < N) l = m + 1;
        else r = m;
    }
    return l % mod;
}

谢谢！

Answer 1

想法是，给定一个数字 m，可以通过将 A 的倍数相加来计算小于或等于 m 的神奇数字的数量（ m / A) 用 B 的倍数 (m / B) 减去 A 和 B 的倍数 (m / lcm)被计算了两次。

现在的解决方案只是最小的数字 m，其中小于或等于 m 的神奇数字的数量恰好是 n。这可以使用二进制搜索找到。

Answer 2

对于给定的数字m，我们可以找出比m小的神奇数字有多少：加上m/A（被A整除的数字的数量小于 m) 和 m/B（可被 B 整除且小于 m 的数字的计数），减去 m/lcm（数字的计数被小于 m 的 A 和 B 整除，以避免重复计算它们）。这里lcm是A和B的最小公倍数；所有能被 A 和 B 整除的数都是 lcm.

的倍数

从这里开始，使用二分查找就很容易了。从足够大的间隔开始（根据问题陈述中提供的输入范围证明初始范围足够大留作 reader 的练习）。找到中间点 m，计算出比中间点小的幻数的个数。如果该计数大于 N，则 m 过冲，我们需要进一步考虑左半部分。否则，m 下冲，我们搜索右半部分。

这种方法可以改进。给定序列 X_i=i*A 和 Y_i=i*B，我们认为序列 Z 是 X 和 Y 的有序并集；我们的任务是找到Z_N。很容易看出 Z 可以用重复模式来描述：在达到 L=lcm(A, B) 之后，相同的模式重复自身向上移动 L，然后再次向上移动 [=42] =] 等等。

例如，如果 A=2 和 B=3，序列 Z 如下所示：

2 3 4 6 | 8 9 10 12 | 14 15 16 18 | ...

很容易看出四个数字的模式，一遍又一遍地重复，每次移动 6 = L = LCM(2, 3)

一般情况下此模式的长度为 M = L/A + L/B - 1：序列 X 中的数字计数为 <= L，加上序列 [=37] 中的数字计数=] 即 <= L，减 1，因为 L 本身被计算了两次。因此，Z_{i+k*M} = Z_i + k*L.

考虑到这一点，找到 Z_N 就足以找到 Z_{N modulo M}。为此，将二进制搜索应用于范围 [1, L] 就足够了——只搜索重复模式的第一次出现，因为序列的其余部分可以很容易地从中导出。

这个解决方案背后的直觉

Intuition behind this solution

c++

algorithm

binary-search