878. Nth Magical Number

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation