class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
}
};
1201. 丑数 III
给你四个整数：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] 的范围内原站题解
javascript 解法, 执行用时: 64 ms, 内存消耗: 41 MB, 提交时间: 2023-07-05 09:43:34
/**
* @param {number} n
* @param {number} a
* @param {number} b
* @param {number} c
* @return {number}
*/
var nthUglyNumber = function(n, a, b, c) {
const ab = lcm(a, b);
const ac = lcm(a, c);
const bc = lcm(b, c);
const abc = lcm(ab, c);
let left = Math.min(a, b, c);
let right = n * left;
while(left < right) {
const mid = Math.floor((left + right) / 2);
const count = low(mid, a) + low(mid, b) + low(mid, c) - low(mid, ab) - low(mid, ac) - low(mid, bc) + low(mid, abc);
if(count >= n) {
right = mid;
}else{
left = mid + 1;
}
}
return right;
}
function low(mid , val) { // 整除保留整数
return mid / val | 0;
}
function lcm(a, b) { //最小公倍数
return a * b / gcd(a, b);
}
function gcd(a, b) { //最大公约数
return b === 0 ? a : gcd(b, a % b);
}
java 解法, 执行用时: 0 ms, 内存消耗: 38.2 MB, 提交时间: 2023-07-05 09:41:11
class Solution {
public int nthUglyNumber(int n, int a, int b, int c) {
long l = 0 , r = (long) n *c;
long ab = lcm(a,b),bc = lcm(b,c),ac = lcm(a,c),abc = lcm(a,bc);
while ( l<r ) {
long m = l+r+1>>1;
long count = m/a+m/b+m/c-m/ab-m/bc-m/ac+m/abc;
if(count>=n) r = m-1;
else l = m;
}
return (int)l+1;
}
// 最大公约数
long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a%b);
}
// 最小公倍数
long lcm(long a, long b) {
return a * b / gcd(a, b);
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 5.9 MB, 提交时间: 2023-07-05 09:39:11
class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
const long long la = a;
const long long lb = b;
const long long lc = c;
const long long lab = lcm(la, lb);
const long long lac = lcm(la, lc);
const long long lbc = lcm(lb, lc);
const long long labc = lcm(lab, lc);
const long long maxabc = max({a, b, c});
// 这里用 lambda 捕获计算好的最小公倍数，避免重复计算
const auto countLessEqual = [=] (long long x) -> long long {
return x / la + x / lb + x / lc - x / lab - x / lac - x / lbc + x / labc;
};
const long long m = countLessEqual(labc);
const long long q = n / m, r = n % m;
long long hi = min(labc, r * maxabc);
long long lo = 0;
while (lo < hi) {
const long long mi = (lo + hi) / 2;
if (countLessEqual(mi) < r)
lo = mi + 1;
else hi = mi;
}
return lo + q * labc;
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-07-05 09:37:31
func nthUglyNumber(n int, a int, b int, c int) int {
ab, ac, bc := lcm(a, b), lcm(a, c), lcm(b, c)
abc := lcm(ab, c)
left, right := 0, n*min(a, b, c)
for left <= right {
mid := (left + right) / 2
num := mid/a + mid/b + mid/c - mid/ab - mid/ac - mid/bc + mid/abc
if num == n {
if mid%a == 0 || mid%b == 0 || mid%c == 0 {
return mid
} else {
right = mid - 1
}
} else if num > n {
right = mid - 1
} else {
left = mid + 1
}
}
return left
}
// 求最小数
func min(a int, args ...int) (result int) {
result = a
for _, v := range args {
if v < result {
result = v
}
}
return result
}
// 求最小公倍数
func lcm(x, y int) int {
return x * y / gcd(x, y)
}
// 求最大公约数
func gcd(x, y int) int {
tmp := x % y
if tmp > 0 {
return gcd(y, tmp)
}
return y
}
python3 解法, 执行用时: 32 ms, 内存消耗: 16 MB, 提交时间: 2023-07-05 09:35:36
class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
from math import lcm
# 最小公倍数
lab, lbc, lac, labc = lcm(a, b), lcm(b, c), lcm(a, c), lcm(a, b, c)
# 计算x是第几个丑数
def countugly(x: int) -> int:
return x // a + x // b + x // c - x // lab - x // lbc - x // lac + x // labc
# 周期优化，对于每一个周期的丑数都是最小公倍数加上第一个周期的丑数
l, r = n // countugly(labc) * labc, (n // countugly(labc) + 1) * labc
while l < r:
m = (l + r) // 2
if countugly(m) < n:
l = m + 1
else:
r = m
return l
python3 解法, 执行用时: 44 ms, 内存消耗: 16.2 MB, 提交时间: 2023-07-05 09:34:02
class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
from math import lcm
# 最小公倍数
lab, lbc, lac, labc = lcm(a, b), lcm(b, c), lcm(a, c), lcm(a, b, c)
# 计算x是第几个丑数
def countugly(x: int) -> int:
return x // a + x // b + x // c - x // lab - x // lbc - x // lac + x // labc
# 二分求值
l, r = 1 , min(min(a, b, c) * n, 2 * pow(10, 9))
while l < r:
m = (l + r) // 2
if countugly(m) < n:
l = m + 1
else:
r = m
return l