Leetcode丑数序列

小于等于某个整数的丑数个数很好计算，即n/a+n/b+n/c-n/ab的最小公倍数-n/ac的最小公倍数-n/bc的最小公倍数+n/三者的最小公倍数
只需要在解空间内二分找到一个整数ans，使得[1, ans]内恰好有n个丑数，ans即为第n个丑数

from math import gcd
class Solution:def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:#三数最小公倍数=两数最小公倍数与第三个数的最小公倍数def Lcm3(x,y,z):a = (x*y)//gcd(x,y)  return (a*z)//gcd(a,z)'''计算有多少个丑数小于等于x+ x整除a,b,c -整除ab,bc,ac最小公倍数 +整除abc最小公倍数 即为所求'''def uglynum(x):return x//a+x//b+x//c-x//(a*b//gcd(a,b))-x//(a*c//gcd(a,c))-x//(b*c//gcd(b,c))+x//Lcm3(a,b,c)'''二分搜索，注意只要uglynum(mid)<n left就=mid+1 所以最后得到的left就是所求例如测试用例2中  a=2,b=3,c=4括号中为丑数                    1,(2),(3),(4),5,(6),7,(8)小于等于它们的丑数个数分别为     0, 1 , 2 , 3 ,3, 4, 4, 5 若n==4如果uglynum(mid)<4 则left一定能直接取到6而不是7'''left=1right=n*min(a,b,c)while left<right:mid=(left+right)//2if uglynum(mid)<n:left=mid+1else:right=midreturn left

作者：CTSCSU
链接：https://leetcode.cn/problems/ugly-number-iii/solution/python-er-fen-cha-zhao-by-ctscsu/
来源：力扣（LeetCode）