1、二分查找

如果我们用函数f(x)f(x)f(x)表示数字小于x的神奇数字的个数，显然我们可以得到如下的公式：f(x)=⌊xa⌋+⌊xb⌋−⌊xc⌋f(x)=\left \lfloor \frac{x}{a} \right \rfloor+\left \lfloor \frac{x}{b} \right \rfloor-\left \lfloor \frac{x}{c} \right \rfloorf(x)=⌊ax​⌋+⌊bx​⌋−⌊cx​⌋，其中c为a和b的最小公倍数。因此我们可以在[a,an][a,a^n][a,an]的区间中进行二分查找并计算当前的f(x)f(x)f(x)的值并与目标值进行比较，最终返回具体的值。

class Solution {
public:const int MOD = 1e9 + 7;int nthMagicalNumber(int n, int a, int b) {long long l = min(a, b);long long r = (long long) n * min(a, b);int c = lcm(a, b);// a和b的最小公倍数while (l <= r) {long long mid = (l + r) / 2;long long cnt = mid / a + mid / b - mid / c;if (cnt >= n) {r = mid - 1;} else {l = mid + 1;}}return (r + 1) % MOD;}
};

2、数学优化

我们可以利用最小公倍数c来缩小n的范围。我们可以计算出f(c)f(c)f(c)的个数为c/a+c/b−1c / a + c / b - 1c/a+c/b−1，因此我们可以化简为f(x)=q∗f(c)+mf(x)=q*f(c)+mf(x)=q∗f(c)+m，因此我们只需要在此基础上查找其后m个神奇数字即可。

class Solution {
public:const int MOD = 1e9 + 7;int nthMagicalNumber(int n, int a, int b) {int c = lcm(a, b);int m = c / a + c / b - 1;int r = n % m;int res = (long long) c * (n / m) % MOD;if (r == 0) {return res;}int addA = a, addB = b;for (int i = 0; i <  r - 1; ++i) {if (addA < addB) {addA += a;} else {addB += b;}}return (res + min(addA, addB) % MOD) % MOD;}
};