Leetcode.1201 丑数 III

题目链接

Leetcode.1201 丑数 III Rating ： 2039

题目描述

给你四个整数：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<=1091 <= n, a, b, c <= 10^91<=n,a,b,c<=109
• 1<=a∗b∗c<=10181 <= a * b * c <= 10^181<=a∗b∗c<=1018
• 本题结果在 [1,2∗109][1, 2 * 10^9][1,2∗109] 的范围内

解法：容斥原理 + 二分

对于 $1,2,3,4,...,n-1,n$ 共 $n$ 个数，能被整数 $k$ 整除的个数为 ⌊nk⌋\\lfloor \\frac{n}{k} \\rfloor⌊kn​⌋。

例如，$n=7$，能被 $k=3$ 整除的个数为 ⌊73⌋=2\\lfloor \\frac{7}{3} \\rfloor = 2⌊37​⌋=2，即 $3,6$。

$lcm(a,b)$ 是 $a$ 和 $b$ 的最小公倍数。

• 定义 $A$ 为 $n$ 中能被 $a$ 整除的数的个数，即 ⌊na⌋\\lfloor \\frac{n}{a} \\rfloor⌊an​⌋
• 定义 $B$ 为 $n$ 中能被 $b$ 整除的数的个数，即 ⌊nb⌋\\lfloor \\frac{n}{b} \\rfloor⌊bn​⌋
• 定义 $C$ 为 $n$ 中能被 $c$ 整除的数的个数，即 ⌊nc⌋\\lfloor \\frac{n}{c} \\rfloor⌊cn​⌋
• 定义 $AB$ 为 $n$ 中能被 $lcm(a,b)$ 整除的数的个数，即 ⌊nlcm(a,b)⌋\\lfloor \\frac{n}{lcm(a,b)} \\rfloor⌊lcm(a,b)n​⌋
• 定义 $BC$ 为 $n$ 中能被 $lcm(b,c)$ 整除的数的个数，即 ⌊nlcm(b,c)⌋\\lfloor \\frac{n}{lcm(b,c)} \\rfloor⌊lcm(b,c)n​⌋
• 定义 $AC$ 为 $n$ 中能被 $lcm(a,c)$ 整除的数的个数，即 ⌊nlcm(a,c)⌋\\lfloor \\frac{n}{lcm(a,c)} \\rfloor⌊lcm(a,c)n​⌋
• 定义 $ABC$ 为 $n$ 中能被 $lcm(a,b,c)$ 整除的数的个数，即 ⌊nlcm(a,b,c)⌋\\lfloor \\frac{n}{lcm(a,b,c)} \\rfloor⌊lcm(a,b,c)n​⌋

故 $n$ 个数中能被 a 或 b 或 c 整除的正整数个数为 ：$cnt=(A+B+C)-(AB+BC+AC)+(ABC)$。

我们用 二分，找到第一个 $cnt\ge n$ 的 $mid$，即 $mid$ 就是第 $n$ 个丑数。

时间复杂度： $logr$

C++代码：

using LL = long long;class Solution {
public:int nthUglyNumber(int n, int a, int b, int c) {LL ab = lcm<LL>(a,b);LL bc = lcm<LL>(b,c);LL ac = lcm<LL>(a,c);LL abc = lcm<LL>(ab,c);LL l = 1 , r = 2e9;while(l < r){LL mid = (r - l) / 2 + l;LL cnt = (mid/a + mid/b + mid/c) - (mid/ab + mid/bc + mid/ac) + (mid/abc);if(cnt >= n) r = mid;else l = mid + 1;}return (int)l;}
};

组词