leetcode: 1201. Ugly Number III [Dichotomy + Mathematics + Inclusion and Exclusion Principle]

分析

Ugly tree sequences cannot be repeated,So it is the union of three multiples
But it's not good,The principle of inclusion and exclusion unfolds
Expansion of the formula using the least common multiple becomes a monotonic non-decreasing onefx
fxThat is, less than or equal toxnumber of ugly trees
Divide to find the first makefx = n的x
It should be noted here that it is less thanl = mid + 1
大于等于r = mid
details

ac code

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        # 数学题 + 容斥原理
        # 小于等于xThe number of ugly numbers is set to f(x)


        # 两个数的最小公倍数
        def lcm(a, b):
            return (a * b) // gcd(a, b)

        # 三个数的最小公倍数
        def lcm3(a, b, c):
            return lcm(lcm(a, b), c)

        # 容斥原理：|A or B or C| = |A| + |B| + |C| - |A and B| - |B and C| - |C and A| + |A and B and C|
        def f(x):
            f1 = x // a + x // b + x // c
            f2 = x // lcm(a, b) + x // lcm(b, c) + x // lcm(c, a)
            f3 = x // lcm3(a, b, c)
            return f1 - f2 + f3
        
        # Divide to find the first makef(x) = n的x 
        # 因为fx单调不减
        l, r = 1, 2 * 10 ** 9
        while l < r:
            mid = (l + r) // 2
            if f(mid) < n:
                l = mid + 1
            else:
                r = mid
        
        return l

总结

The principle of inclusion and exclusion simplifies the problem Dichotomous solution