[LeetCode]Nth Magical Number

Brute Force的做法就是一个一个枚举，枚举到第N大的，但显然这道题的数据量不允许我们这么做。我们可以观察出一点，magical number是周期性增加的，这个周期就是A和B的LCM(lowest common multiple，LCM(A, B) = A * B / GCD(A, B), GCD为最小公倍数)，从0开始，每增加一个LCM，就会增加m = LCM/A + LCM/B - 1个magic number。我们我们可以把问题转化成N = a * m + b，a很好求，只需要求b即可。我们就可以把问题转化成求第b个magical number。时间复杂度取决于找第b个magical number的时间，最坏的情况就是A和B互质的，并且b = m - 1，这种情况下时间复杂度O(A + B)，代码如下：


另一个做法，对于给定的数字M，我们其实可以很容易求出有多少小于等于M的magical number，这个值为M/A + M/B - M/LCM(A, B)，这个很好理解，就是每个A的倍数和每个B的倍数，减去重复的。这样的话我们可以在常数时间内确定给定的数相对于target是偏大还是偏小，用binary search找即可。时间复杂度log(N * max(A, B))，代码如下：