Time: 20190922
Type: Medium
题目描述
请你帮忙设计一个程序，用来找出第 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, 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^9
1 <= a * b * c <= 10^18
本题结果在 [1, 2 * 10^9] 的范围内。
思路
这道题用到了奥数四大定理之一：容斥定理。
从1到n能被a或b或者c整除的个数是：
被a整除的个数 + 被b整除的个数 + 被c整除的个数 – 能被a和b同时整除的个数 – 能被a和c同时整除的个数 – 能被b和c同时整除的个数 + 同时被a, b, c整除的个数。
因为计算个数就是个数学公式，我们就可以用二分法，从1到max(a, b, c) * n之间查找了。
代码
class Solution:def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:# 最大公约数def gcd(a, b): if (a == 0): return b return gcd(b % a, a) # 最小公倍数def lcm(a, b): return ((a * b) // gcd(a, b)) # 从1到num，能被a或b或c整除的数的个数# 容斥定理# 奥数四大定理之一def divTermCount(a, b, c, num): # http://www.pianshen.com/article/8305144485/# num // a: 被a整除的个数# num // b: 被b整除的个数# num // c: 被c整除的个数# 减掉能被a和b同时整除的个数# 减掉能被a和c同时整除的个数# 减掉能被b和c同时整除的个数# 加上同时被a, b, c整除的个数return ((num // a) + (num // b) + (num // c) - (num // lcm(a, b)) - (num // lcm(b, c)) - (num // lcm(a, c)) + (num // lcm(a, lcm(b, c)))) # 二分搜索法def findNthTerm(a, b, c, n): low = 1high = max(a, b, c) * nmid = 0while (low < high): mid = low + (high - low) // 2if (divTermCount(a, b, c, mid) < n): low = mid + 1else: high = mid return low return findNthTerm(a,b,c,n)
2019.10 Update:
第一届PAT算法直播课培训班招募帖，欢迎点击查看详情、
END.