LC 100267. 单面值组合的第 K 小金额

https://leetcode.cn/problems/kth-smallest-amount-with-single-denomination-combination/description/

这个应该是一个比较简单的组合问题，但是之前没有系统化地考虑过怎么做，其实大致思路就是

这个试过其他思路好像都不行，都会存在计算错误。但是这种方法也就是适合ways = n比较少的cases. 如果N = 15的话，那么 `ops` 的数量大约是在10k左右（我估计的），外面一层二分其实就还好。 

class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        def gcd(a, b):
            while b != 0:
                a, b = b, a % b
            return a

        def lcm(a, b):
            return (a * b) // gcd(a, b)

        def precompute():
            ops = []
            n = len(coins)
            for sz in range(1, n + 1):
                import itertools
                op = []
                for xs in itertools.combinations(coins, sz):
                    l = 1
                    for x in xs:
                        l = lcm(x, l)
                    op.append(l)
                ops.append(op)
            return ops

        ops = precompute()

        def test(value):
            res = 0
            for idx, op in enumerate(ops):
                sign = 1 if idx % 2 == 0 else -1
                r = 0
                for x in op:
                    r += value // x
                res += r * sign
            return res

        coins.sort()
        s, e = 0, k * coins[-1]
        while s <= e:
            m = (s + e) // 2
            r = test(m)
            # print(m, r)
            if r >= k:
                e = m - 1
            else:
                s = m + 1
        return s