[LeetCode] 878. Nth Magical Number

[grandyang]

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.

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

Note:

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

这道题定义了一种神奇正整数，就是能同时被给定的正整数A或B整除的数，让我们返回第N个神奇的数字，暗示了这个数字可能很大，要对一个超大数取余。又是对这个 1e9+7 取余，博主下意识的反应是用动态规划 Dynamic Programming 来做，但其实是不能的，因为每个数字能不能被A或B整除是相对独立的，并不会跟之前的状态有联系，这样就不好写出状态转移方程了，所以这并不是一道 DP 题。首先来想，对于 [1, n] 中的数，能整除A的有多少个，举例来说吧，假如 n=17，A=2，那么 17 以内能整除2的就有 2，4，6，8，10，12，14，16，这八个数字，貌似正好是 n/A=17/2=8。再来看其他例子，比如 n=17，B=3，那么 17 以内能整除3的就有 3，6，9，12，15，这五个数字，貌似也是 n/B=17/3=5。那么能被A或B整除的个数呢，比如 n=17，A=2，B=3，那么 17 以内能整除2或3的数字有 2，3，4，6，8，9，10，12，14，15，16，这十一个数字，并不是 n/A + n/B = 8+5 = 13，为啥呢？因为有些数字重复计算了，比如 6，12，这两个数字都加了两次，我们发现这两个数字都是既可以整除A又可以整除B的，只要把这两个数字减去 13-2=11，就是所求的了。怎么找同时能被A和B整除的数呢，其实第一个这样的数就是A和B的最小公倍数 Least Common Multiple，所有能被A和B的最小公倍数整除的数字一定能同时整除A和B。那么最小公倍数 LCM 怎么算呢？这应该是小学数学的知识了吧，就是A乘以B除以最大公约数 Greatest Common Divisor，这个最大公约数就不用多说了吧，也是小学的内容，是最大的能同时整除A和B的数。

明白了这些，我们就知道了对于任意小于等于数字x的且能被A或B整除的正整数的个数为 x/A + x/B - x/lcm(A,B)。所以我们需要让这个式子等于N，然后解出x的值即为所求。直接根据式子去求解x得到的不一定是正整数，我们可以反其道而行之，带确定的x值进入等式，算出一个结果，然后跟N比较大小，根据这个大小来决定新的要验证的x值，这不就是典型的二分搜索法么。确定了要使用 Binary Search 后，就要来确定x值的范围了，x值最小能取到A和B中的较小值，由于A和B最小能取到2，所以x的最小值也就是2。至于最大值，还是根据上面的等式，x能取到的最大值是 N*min(A,B)，根据题目中N和A，B的范围，可以推出最大值不会超过 1e14，这个已经超过整型最大值了，所以我们初始化的变量都要用长整型。然后就是进入 while 循环了，判定条件是上面写的那个等式，其实这是博主之前的总结帖 LeetCode Binary Search Summary 二分搜索法小结 中的第四类，用子函数当作判断关系，不是简单的用 mid 来判断，而是要通过 mid 来计算出需要比较的值。若计算值比N小，则去右半段，反之左半段，最后别忘了对M取余即可，参见代码如下：

解法一：

class Solution {
public:
    int nthMagicalNumber(int N, int A, int B) {
        long lcm = A * B / gcd(A, B), left = 2, right = 1e14, M = 1e9 + 7;
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (mid / A + mid / B - mid / lcm < N) left = mid + 1;
            else right = mid;
        }
        return right % M;
    }
    int gcd(int a, int b) {
        return (b == 0) ? a : gcd(b, a % b);
    }
};

下面这种方法就比较 tricky 了，完全是利用数学功底来解的，连二分搜索都不用，常数级的时间复杂度，碉堡了有木有？！这里主要是参考了大神 jianwu 的帖子，博主也不能说是完全理解透彻了，尝试着去讲解一下吧。我们用这个例子来讲解吧 A=3，B=5，N=10，前面的分析提到了，只有在A和B的最小公倍数 LCM 处，或者是能除以这个 LCM 的数字的地方，才会出现重复。3和5的最小公倍数是 15，所以对于所有小于15的数字x，能整除A的数字有 x/A 个，能整除B的数字有 x/B 个，若把每一个 LCM 看作一个 block 的话，这个区间内分别能整除A和B的数字是没有重复的，所以这个区间的长度是 len = lcm/A + lcm/B - 1 = 15/3 + 15/5 - 1 = 7。下面要算的就是N里面有多少个 block，并且余数是多少，因为我们可以通过 LCM 快速来定位 block 的边界位置，只要知道了偏移量，就能求出正确的神奇数字了。block 的个数是通过 N/len = 10/7 = 1，余数是通过 N%len = 10%7 = 3 计算的。我们可以通过 block 的个数和长度快速定位到 15，这里是不能直接加上余数3的，因为余数表示的是 15 后面的第三个能被3或5整除的数，18，20，21，所以答案是 21，这里我们需要算出这个偏移量 21-15=6，从而才能得到正确结果。怎么计算呢？想一下，15 后面第三个能被3整除的数是 18，21，24，所以只看3的话偏移量是 3/(1.0/3)=9，而 15 后面第三个能被5整除的数是 20，25，30，偏移量是 3/(1.0/5)=15，但是正确的偏移量应该是考虑两种情况的总和，所以应该是 nearest=3/(1.0/3 + 1.0/5)=5.625，但我们的偏移量一定要是个整数，所以我们再用一个取整的过程 min(ceil(nearest/3) x 3, ceil(nearest/5) x 5) = 6，最终就可以得到正确的偏移量，加上 15，就是正确的结果了，参见代码如下：
解法二：

class Solution {
public:
    int nthMagicalNumber(int N, int A, int B) {
        long lcm = A * B / gcd(A, B), M = 1e9 + 7;
        long len = lcm / A + lcm / B - 1, cnt = N / len, rem = N % len;
        double nearest = rem / (1.0 / A + 1.0 / B);
        int remIdx = min(ceil(nearest / A) * A, ceil(nearest / B) * B);
        return (cnt * lcm + remIdx) % M;
    }
    int gcd(int a, int b) {
        return (b == 0) ? a : gcd(b, a % b);
    }
};

Github 同步地址:

#878

参考资料：

https://leetcode.com/problems/nth-magical-number/

https://leetcode.com/problems/nth-magical-number/discuss/154613/C%2B%2BJavaPython-Binary-Search

https://leetcode.com/problems/nth-magical-number/discuss/154965/o(1)-Mathematical-Solution-without-binary-or-brute-force-search

LeetCode All in One 题目讲解汇总(持续更新中...)