1201. Ugly Number III

https://leetcode.com/problems/ugly-number-iii/

最开始看到这题我有点懵,分析了很久才理清思路:

如果只有a, b两个元素,比较好搞:

但是如果是a, b, c三个元素,如何各项的正负号,尤其是lcm(a, b, c)的正负号. 各项应该是这样的:

我觉得可以针对一个值分析,就是lcm(a, b, c), 计算它被计入的次数:

  1. 在第一项,他们被计入了+3次。
  2. 在第二项,他们被计入了-3次。
  3. 而他们应该只被计入1次,所以第三项系数应该是1,符号是正号。
def lcm(x, y):
    return x * y // gcd(x, y)

def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

def test(abc):
    a, b, c = abc
    Gab = lcm(a, b)
    Gac = lcm(a, c)
    Gbc = lcm(b, c)
    Gabc = lcm(Gab, c)

    s, e = 1, n
    found = False
    while s <= e:
        m = (s + e) // 2
        x = m + (a * m) // b + (a * m) // c
        y = (a * m) // Gab + (a * m) // Gac + (a * m) // Gbc
        z = (a * m) // Gabc
        seq = x - y + z
        if seq == n:
            found = True
            break
        elif seq > n:
            e = m - 1
        else:
            s = m + 1
    return found, a * m