Readme

3116.Kth-Smallest-Amount-With-Single-Denomination-Combination

本题就是求第k个能被coins里任意一个元素整除的自然数。

因为我们无法枚举每个符合条件的自然数直至第k个，我们只能用二分搜值的框架。猜测一个M，计算M以内符合条件的自然数有多少，多了就降低M，少了就抬升M，直至找到恰好的M。

那么如何计算M以内、能被coins里任意一个元素整除的自然数的个数呢？显然我们会用容斥原理。能被任意一个元素整除的个数 = sum(能被每一个元素整除的个数) - sum(能被每两个元素同时整除的个数) + sum(能被每三个元素同时整除的个数) - sum(能被每四个元素同时整除的个数) + ...

举个例子，能被a,b,c三个元素同时整除的个数，是 M / lcm(a,b,c)，其中lcm是三者的最小公倍数。如果想在m个元素里，枚举任意三个元素的组合，那么我们会用gospher's hack，高效枚举中一个长度为m的二进制数里含有三个bit 1的mask。