英文原文
An ugly number is a positive integer that is divisible by a, b, or c.
Given four integers n, a, b, and c, return the nth ugly number.
Example 1:
Input: n = 3, a = 2, b = 3, c = 5 Output: 4 Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.
Example 2:
Input: n = 4, a = 2, b = 3, c = 4 Output: 6 Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.
Example 3:
Input: n = 5, a = 2, b = 11, c = 13 Output: 10 Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.
Example 4:
Input: n = 1000000000, a = 2, b = 217983653, c = 336916467 Output: 1999999984
Constraints:
1 <= n, a, b, c <= 1091 <= a * b * c <= 1018- It is guaranteed that the result will be in range
[1, 2 * 109].
中文题目
给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。
丑数是可以被 a 或 b 或 c 整除的 正整数 。
示例 1：
输入：n = 3, a = 2, b = 3, c = 5 输出：4 解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
示例 2：
输入：n = 4, a = 2, b = 3, c = 4 输出：6 解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。
示例 3：
输入：n = 5, a = 2, b = 11, c = 13 输出：10 解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
示例 4：
输入：n = 1000000000, a = 2, b = 217983653, c = 336916467 输出：1999999984
提示：
1 <= n, a, b, c <= 10^91 <= a * b * c <= 10^18- 本题结果在
[1, 2 * 10^9]的范围内
通过代码
高赞题解
基础思路
首先，为什么第一时间能想到二分法？
让我们观察题目，可以看到，最终状态(即n)的范围非常大。试图自底向上递推或是按照通常的自顶向下回溯显然会超时(比如动态规划、DFS等方法)
面对这么大的状态空间，二分法的时间复杂度是logN,因此能够大大压缩需要遍历的状态数目
思路剖析
既然已经确定了二分法作为切入点，关键问题来了，如何二分呢？
按照题意，所谓丑数是可以至少被a、b、c三者中的一者整除的，那么对于一个丑数X，我们能够确定它是第几个丑数吗？
–答案显然是可以的，我们只需要计算X中包含了多少个丑数因子即可。
即只需要知道在[0,X]范围内,还有多少个丑数即可，而这些丑数，无非就是一些能被a或者b或者c所整除的数。
那么显然，我们直接用X/a、X/b、X/c就能计算出[0,X]范围内有多少数能被a或者b或者c整除，然后把它们加起来就是答案！
但是仔细思考一下，我们是不是重复计算了些什么？如果一个数既能被a整除，又能被b整除，那么实际上该数在先前的计算中就被重复计算了一次(分别是在计算X/a和X/b时)。
–好吧，让我们思考所有可能的情况
1.该数只能被a整除 (该数一定是a 的整数倍)
2.该数只能被b整除 (该数一定是b 的整数倍)
3.该数只能被c整除 (该数一定是c 的整数倍)
4.该数只能被a和b同时整除 (该数一定是a、b最小公倍数的整数倍)
5.该数只能被a和c同时整除 (该数一定是a、c最小公倍数的整数倍)
6.该数只能被b和c同时整除 (该数一定是b、c最小公倍数的整数倍)
7.该数只能被a和b和c同时整除（该数一定是a、b、c的最小公倍数的整数倍）
所以，我们只需要分别计算以上七项就能得到结果了！让我们分别来看（用MCM+下标表示最小公倍数）：
情况1 = X/a - 情况4 - 情况5 - 情况7
情况2 = X/b - 情况4 - 情况6 - 情况7
情况3 = X/c - 情况5 - 情况6 - 情况7
情况4 = X/MCM_a_b - 情况7
情况5 = X/MCM_a_c - 情况7
情况6 = X/MCM_b_c - 情况7
情况7 = X/MCM_a_b_c
让我们整理上述方程后也就得到：
sum(情况) = X/a + X/b + X/c - X/MCM_a_b - X/MCM_a_c - X/MCM_b_c + X/MCM_a_b_c
好了，现在也就得到了计算X中包含多少个丑数因子的方法了！
至于计算最小公倍数的方法，这里不多介绍，概括而言就是对于两个数a和b，它们的最小公倍数 = a*b/(a和b的最大公约数)，最大公约数可以通过辗转相除法得到
二分搜索
在得到了计算任意数中包含了多少个丑数因子的方法后，我们实际上只需要通过二分法，不断缩小边界范围，直到某个位置所对应的数恰好包含了n个丑数因子为止。
注意，通过二分法计算的答案并非是最终答案，因为可以有很多数同时包含有n个丑数因子！
比如第n个丑数是X，那么[X,X + min(a,b,c))这个半开区间内的所有数都同时包含n个丑数因子，我们通过二分法得到的答案也随机分布于这个区间中。而实际上我们只需要得到该区间的左端即可。处理方法很简单：假设我们得到的临时答案是K(K∈[X,X + min(a,b,c))),那么K - min(K%a,K%b,K%c) = X.也就是只需要把临时答案减去其与a、b、c三者中取余的最小值即可！
代码
class Solution {
public:
using LL = long long;
int nthUglyNumber(int n, int a, int b, int c) {
//看到n的范围应该马上联想到是，典型的二分思路
LL low = min(min(a,b),c); //下边界显然是a、b、c中最小者
LL high = static_cast<LL>(low) * n; //上边界是这个最小者的n倍
LL res = Binary_Search(low,high,a,b,c,n);
LL left_a = res%a;
LL left_b = res%b;
LL left_c = res%c;
return res - min(left_a,min(left_b,left_c));
}
//二分搜索
LL Binary_Search(LL low,LL high,int a,int b,int c,LL n){
if(low >= high) return low;
LL mid = (low + high)>>1;
LL MCM_a_b = MCM(a,b);
LL MCM_a_c = MCM(a,c);
LL MCM_b_c = MCM(b,c);
LL MCM_a_b_c = MCM(MCM_a_b,c);
//独立的丑数个数为，当前数分别除以a、b、c的和，减去当前数除以a、b、c两两间最小公倍数的和，再加上当前数除以 a、b、c三者的最小公倍数
LL count_n = mid/a + mid/b + mid/c - mid/MCM_a_b - mid/MCM_b_c - mid/MCM_a_c + mid/MCM_a_b_c;
if(count_n == n) return mid;
if(count_n < n) return Binary_Search(mid + 1,high,a,b,c,n);
return Binary_Search(low,mid-1,a,b,c,n);
}
//求最小公倍数：两数乘积除以最大公约数
LL MCM(LL a,LL b){
LL Multi = a * b;
while(b > 0){
LL tmp = a % b;
a = b;
b = tmp;
}
return Multi/a;
}
};统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 6337 | 25434 | 24.9% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
