Leetcode 878. 第 N 个神奇数字

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。

 

示例 1：

输入：n = 1, a = 2, b = 3
输出：2

示例 2：

输入：n = 4, a = 2, b = 3
输出：6

 

提示：

    1 <= n <= 109
    2 <= a, b <= 4 * 104

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 解法一：二分查找

  前置知识：
  1~i中能够被a整除的数个数为 i/a, 能够被b整除的个数为i/b
  
  那么1~i种能被a或b整除的数个数之和是i/a + i/b吗？显然不是，因为还有既能被a整除也能被b整除的数。
  
  怎么减去这些重复的个数呢？
  
  可以发现既能被a整除也能被b整除的数必然是a和b的公倍数，那么我们求出最小公倍数c = Lcm(a, b)。
  
  1~i中可以被c整除个数为i/c,因此被a或b整除的数个数之和 i/a + i/b - i/c。
  
  如何利用以上信息计算答案呢?
  
  题目需要返回第n个神奇数字，由于n很大，直接暴力求解显然不行。
  
  但是其实明白了上面的信息后，很容易就可以想到二分法来求解答案。
  
  可以将题目转化为：在1~i中求解能被a或b整除的数个数之和大于等于n的最小的i即是我们的答案。
  
  显然对于答案x来说，1~x-1必然是不满足要求，而x~INF都能够满足要求。
  
  那么就可以使用二分法来寻找这个问题的边界,左边界为第一个神奇数字min(a, b)，右边界为min(a,b) * n,即必然有大于等于n个神奇数字。
  

• 时间复杂度：$O(log(n\ast min(a,b)))$

• 空间复杂度：$O(1)$

class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        long l = Math.min(a, b), r = (long)Math.min(a, b) * n, c = lcm(a, b); 
        while (l < r) {
            long mid = (l + r) / 2;
            if (mid / a + mid / b - mid / c >= n) r = mid;
            else l = mid + 1;
        }
        return (int) (r % (1000000007));
    }
    int lcm(int a, int b) {return a / gcd(a, b) * b;}
    int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int nthMagicalNumber(int n, int a, int b) {
        long long l = min(a, b), r = (long long)min(a, b) * n, c = lcm(a, b); 
        while (l < r) {
            long mid = (l + r) / 2;
            mid / a + mid / b - mid / c >= n ? r = mid : l = mid + 1;
        }
        return (int) (r % (1000000007));
    }
    int lcm(int a, int b) {return a / gcd(a, b) * b;}
    int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
};
1
2
3
4
5
6
7
8
9
10
11
12
13

• 二分模板
  二分本质：寻找问题的边界
  在[L, R]区间定义某种性质，可以将区间分为两个部分，左边是不满足该性质，右边满足该性质
  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-evYkUA0a-1669045362799)(https://pic.leetcode.cn/1669040203-kQxceJ-%E5%9B%BE%E7%89%87.png)]

//寻找绿色边界点
//区间分为[l, mid] 和 [mid + 1, r]  
int l = 0, r = n - 1;
while (l < r) {  /
    int mid = (l + r) >> 1; // 由于mid在左边边区间所以不用+1
    if (check(mid)) {//为true代表mid在绿色区间
        r = mid; //缩小区间到[l, mid]
    } else l = mid + 1; //为false 代表mid在红色区间，缩小区间到[mid+1, r]
}
//循环结束后 r位于红色边界点上

//寻找红色边界点
//区间分为[l, mid - 1] 和 [mid, r]  
int l = 0, r = n - 1;
while (l < r) {  /
    int mid = (l + r + 1) >> 1; // 由于mid在右边区间所以要+1
    if (check(mid)) {//为true代表mid在红色区间
        l = mid; //缩小区间到[mid, r]
    } else r = mid - 1; //为false 代表mid在绿色区间，缩小区间到[l, mid-1]
}
//循环结束后 r位于红色边界点上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 对于解法一的问题，定义性质为：神奇数字个数大于等于n为绿色边界。那么显然需要寻找绿色边界点。

• 解法二：数学推导

  我们已知$c=lcm(a,b)$, 那么对于一个未知数$x$, $1$~$xc$范围内能够被$a$或$b$整除的数个数为$cnt=(xc/a+xc/b-xc/c)=x(c/a+c/b-1)$，其中$xc$就是第$cnt$个神奇数字。
  
  这时候，我们可以令$m=(c/a+c/b-1)$,即$cnt=xm$
  
  我们再令题目给定的$n=xm+res$
  
  通过定义的式子可以知道$xm$应该小于等于n,我们找到最大的满足要求的$x=n/m$,这时候可知$0\le rec<m$
  
  那么题目至此可以转化为：在$xm$个神奇数字后面再寻找res个神奇数字，这个寻找res个数字的操作就可以在有限时间内完成。
  
  对于个数$xm$后面的神奇数字一定比$xc$大，因为$1$~$xc$神奇数字个数为$xm$,那么我们只需要从$xc$后寻找$res$个神奇数字，即$xc+a,xc+2a,...和xc+b,xc+2b...$中比较寻找。
  

• 时间复杂度：$O(m)=O(c/a+c/b-1)=O(b+a-1)=O(a+b)$

• 空间复杂度：$O(1)$

 class Solution {
    int mod = 1000000007;
    public int nthMagicalNumber(int n, int a, int b) {
        long c = lcm(a, b), m = (c / a + c /b - 1), x = n / m, r = n - x * m;
        if (r == 0) return (int)(x * c % mod); //代表r=0,那么xc就是第n个神奇数字
        //从xc后面寻找r个神奇数字数字 xc+a,xc+2a..., xc+b,xc+2b...
        long ta = x * c + a, tb = x * c + b;
        while (--r > 0) {
            if (ta > tb) tb += b;
            else ta += a; 
        } 
        return (int)(Math.min(ta, tb) % mod);
    }
    int lcm(int a, int b) {return a / gcd(a, b) * b;}
    int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int mod = 1000000007;
    int nthMagicalNumber(int n, int a, int b) {
        long long c = lcm(a, b), m = (c / a + c /b - 1), x = n / m, r = n - x * m;
        if (r == 0) return (int)(x * c % mod); //代表r=0,那么xc就是第n个神奇数字
        //从xc后面寻找r个神奇数字数字 xc+a,xc+2a..., xc+b,xc+2b...
        long long ta = x * c + a, tb = x * c + b;
        while (--r > 0) ta > tb ? tb += b: ta += a; 
        return (int)(min(ta, tb) % mod);
    } 
    int lcm(int a, int b) {return a / gcd(a, b) * b;}
    int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 解法三：数学推理 + 二分
  通过对解法二的思考，可以发现$xm$将整个n个神奇数字划分为x段,每段的最后一个神奇数字都是LCM的倍数。
  

  例如：给定a=2,b=3,c=6
  x=1: 2,3,4,6
  x=2: 8,9,10,12
  x=3: 14,15,16,18
  1
  2
  3
  4

  每个区间个数$m=(c/a+c/b-1)=(b+a-1)$
  
  可以知道n必然位于第x+1个区间上某个数(若能被整除，那么答案便是$xc$)。
  
  将二分区间缩小为$[xc+1,xc+c]$寻找第n个神奇数字数字。
  
• 时间复杂度：$O(log(c)),c=lcm(a,b)$
• 空间复杂度：$O(1)$

 class Solution {
    int mod = 1000000007;
    int nthMagicalNumber(int n, int a, int b) {
        long c = lcm(a, b), m = (c / a + c /b - 1), x = n / m, res = n - x * m;
        if (res == 0) return (int)(x * c % mod); //代表r=0,那么xc就是第n个神奇数字
        long l = x * c + 1, r = x * c + c;
        while (l < r) {
            long mid = (l + r) / 2;
            if (mid / a + mid / b - mid / c >= n) r = mid;
            else l = mid + 1;
        }  
        return (int)(r % mod);
    } 
    int lcm(int a, int b) {return a / gcd(a, b) * b;}
    int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int mod = 1000000007;
    int nthMagicalNumber(int n, int a, int b) {
        long long c = lcm(a, b), m = (c / a + c /b - 1), x = n / m, res = n - x * m;
        if (res == 0) return (int)(x * c % mod); //代表r=0,那么xc就是第n个神奇数字
        long long l = x * c + 1, r = x * c + c;
        while (l < r) {
            long mid = (l + r) / 2;
            mid / a + mid / b - mid / c >= n ? r = mid : l = mid + 1;
        }  
        return (int)(r % mod);
    } 
    int lcm(int a, int b) {return a / gcd(a, b) * b;}
    int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16