LC 1201. Ugly Number III

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

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

首先这个数肯定是 a*n or b*n or c*n, 关键就是我们确定这个n
然后对于a * n, 中间可能还有许多可以整除b, c的元素，所以实际上 a * n肯定是 m-th ugly number, 并且m >= n.
我们可以先猜测是 a*n, 然后计算a*n是 mth-ugly number, 然后使用二分法逼近

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

对于 a*n , 期间有 a*n / b个元素是被b整除的
然后需要减去 a*n / lcm(a, b)
m = n + an / b - an / lcm(a, b)

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

n, an/b, an/c. 这个是正号
an/lcm(a,b), an/lcm(b,c), an/(a,c). 这些都是负号
an/lcm(a, b, c). 这个是正号还是负号？有没有额外系数？

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

在第一项，他们被计入了+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