一个正整数如果能被 a 或 b 整除，那么它是神奇的。给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。示例 1：输入：n = 1, a = 2, b = 3输出：2示例 2：输入：n = 4, a = 2, b = 3输出：6提示：1 <= n <= 1092 <= a, b <= 4 * 104
解法一：二分查找
前置知识：
1~i中能够被a整除的数个数为 i/a, 能够被b整除的个数为i/b
那么1~i种能被a或b整除的数个数之和是i/a + i/b吗？显然不是，因为还有既能被a整除也能被b整除的数。
怎么减去这些重复的个数呢？
可以发现既能被a整除也能被b整除的数必然是a和b的公倍数，那么我们求出最小公倍数c = Lcm(a, b)。
1~i中可以被c整除个数为i/c,因此被a或b整除的数个数之和 i/a + i/b - i/c。
如何利用以上信息计算答案呢?
题目需要返回第n个神奇数字，由于n很大，直接暴力求解显然不行。
但是其实明白了上面的信息后，很容易就可以想到二分法来求解答案。
可以将题目转化为：在1~i中求解能被a或b整除的数个数之和大于等于n的最小的i即是我们的答案。
显然对于答案x来说，1~x-1必然是不满足要求，而x~INF都能够满足要求。
那么就可以使用二分法来寻找这个问题的边界,左边界为第一个神奇数字min(a, b)，右边界为min(a,b) * n,即必然有大于等于n个神奇数字。
时间复杂度：O(log(n∗min(a,b)))O(log(n* min(a, b)))O(log(n∗min(a,b)))
空间复杂度：O(1)O(1)O(1)
class Solution {public int nthMagicalNumber(int n, int a, int b) {long l = Math.min(a, b), r = (long)Math.min(a, b) * n, c = lcm(a, b); while (l < r) {long mid = (l + r) / 2;if (mid / a + mid / b - mid / c >= n) r = mid;else l = mid + 1;}return (int) (r % (1000000007));}int lcm(int a, int b) {return a / gcd(a, b) * b;}int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}}
class Solution {public:int nthMagicalNumber(int n, int a, int b) {long long l = min(a, b), r = (long long)min(a, b) * n, c = lcm(a, b); while (l < r) {long mid = (l + r) / 2;mid / a + mid / b - mid / c >= n ? r = mid : l = mid + 1;}return (int) (r % (1000000007));}int lcm(int a, int b) {return a / gcd(a, b) * b;}int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}};
二分模板
二分本质：寻找问题的边界
在[L, R]区间定义某种性质，可以将区间分为两个部分，左边是不满足该性质，右边满足该性质
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-evYkUA0a-1669045362799)(/1669040203-kQxceJ-%E5%9B%BE%E7%89%87.png)]
//寻找绿色边界点//区间分为[l, mid] 和 [mid + 1, r] int l = 0, r = n - 1;while (l < r) {/int mid = (l + r) >> 1; // 由于mid在左边边区间所以不用+1if (check(mid)) {//为true代表mid在绿色区间r = mid; //缩小区间到[l, mid]} else l = mid + 1; //为false 代表mid在红色区间，缩小区间到[mid+1, r]}//循环结束后 r位于红色边界点上//寻找红色边界点//区间分为[l, mid - 1] 和 [mid, r] int l = 0, r = n - 1;while (l < r) {/int mid = (l + r + 1) >> 1; // 由于mid在右边区间所以要+1if (check(mid)) {//为true代表mid在红色区间l = mid; //缩小区间到[mid, r]} else r = mid - 1; //为false 代表mid在绿色区间，缩小区间到[l, mid-1]}//循环结束后 r位于红色边界点上
对于解法一的问题，定义性质为：神奇数字个数大于等于n为绿色边界。那么显然需要寻找绿色边界点。
解法二：数学推导
我们已知c=lcm(a,b)c = lcm(a, b)c=lcm(a,b), 那么对于一个未知数xxx, 111~xcxcxc范围内能够被aaa或bbb整除的数个数为cnt=(xc/a+xc/b−xc/c)=x(c/a+c/b−1)cnt =(xc/a + xc/b - xc/c) = x(c/a + c/b -1)cnt=(xc/a+xc/b−xc/c)=x(c/a+c/b−1)，其中xcxcxc就是第cntcntcnt个神奇数字。
这时候，我们可以令m=(c/a+c/b−1)m = (c/a + c/b -1)m=(c/a+c/b−1),即cnt=xmcnt=xmcnt=xm
我们再令题目给定的n=xm+resn = xm + resn=xm+res
通过定义的式子可以知道xmxmxm应该小于等于n,我们找到最大的满足要求的x=n/mx = n / mx=n/m,这时候可知0≤rec<m0 \le rec <m0≤rec<m
那么题目至此可以转化为：在xmxmxm个神奇数字后面再寻找res个神奇数字，这个寻找res个数字的操作就可以在有限时间内完成。
对于个数xmxmxm后面的神奇数字一定比xcxcxc大，因为111~xcxcxc神奇数字个数为xmxmxm,那么我们只需要从xcxcxc后寻找resresres个神奇数字，即xc+a,xc+2a,...和xc+b,xc+2b...xc+a,xc+2a,...和xc+b,xc+2b...xc+a,xc+2a,...和xc+b,xc+2b...中比较寻找。
时间复杂度：O(m)=O(c/a+c/b−1)=O(b+a−1)=O(a+b)O(m) = O(c/a + c/b - 1) = O(b + a - 1) = O(a + b)O(m)=O(c/a+c/b−1)=O(b+a−1)=O(a+b)
空间复杂度：O(1)O(1)O(1)
class Solution {int mod = 1000000007;public int nthMagicalNumber(int n, int a, int b) {long c = lcm(a, b), m = (c / a + c /b - 1), x = n / m, r = n - x * m;if (r == 0) return (int)(x * c % mod); //代表r=0,那么xc就是第n个神奇数字//从xc后面寻找r个神奇数字数字 xc+a,xc+2a..., xc+b,xc+2b...long ta = x * c + a, tb = x * c + b;while (--r > 0) {if (ta > tb) tb += b;else ta += a; } return (int)(Math.min(ta, tb) % mod);}int lcm(int a, int b) {return a / gcd(a, b) * b;}int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}}
class Solution {public:int mod = 1000000007;int nthMagicalNumber(int n, int a, int b) {long long c = lcm(a, b), m = (c / a + c /b - 1), x = n / m, r = n - x * m;if (r == 0) return (int)(x * c % mod); //代表r=0,那么xc就是第n个神奇数字//从xc后面寻找r个神奇数字数字 xc+a,xc+2a..., xc+b,xc+2b...long long ta = x * c + a, tb = x * c + b;while (--r > 0) ta > tb ? tb += b: ta += a; return (int)(min(ta, tb) % mod);} int lcm(int a, int b) {return a / gcd(a, b) * b;}int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}};
解法三：数学推理 + 二分
通过对解法二的思考，可以发现xmxmxm将整个n个神奇数字划分为x段,每段的最后一个神奇数字都是LCM的倍数。
例如：给定a=2,b=3,c=6x=1: 2,3,4,6x=2: 8,9,10,12x=3: 14,15,16,18
每个区间个数m=(c/a+c/b−1)=(b+a−1)m = (c/a + c/b - 1) = (b + a - 1)m=(c/a+c/b−1)=(b+a−1)
可以知道n必然位于第x+1个区间上某个数(若能被整除，那么答案便是xcxcxc)。
将二分区间缩小为[xc+1,xc+c][xc+1,xc + c][xc+1,xc+c]寻找第n个神奇数字数字。
时间复杂度：O(log(c)),c=lcm(a,b)O(log(c)), c = lcm(a,b)O(log(c)),c=lcm(a,b)空间复杂度：O(1)O(1)O(1)
class Solution {int mod = 1000000007;int nthMagicalNumber(int n, int a, int b) {long c = lcm(a, b), m = (c / a + c /b - 1), x = n / m, res = n - x * m;if (res == 0) return (int)(x * c % mod); //代表r=0,那么xc就是第n个神奇数字long l = x * c + 1, r = x * c + c;while (l < r) {long mid = (l + r) / 2;if (mid / a + mid / b - mid / c >= n) r = mid;else l = mid + 1;} return (int)(r % mod);} int lcm(int a, int b) {return a / gcd(a, b) * b;}int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}}
class Solution {public:int mod = 1000000007;int nthMagicalNumber(int n, int a, int b) {long long c = lcm(a, b), m = (c / a + c /b - 1), x = n / m, res = n - x * m;if (res == 0) return (int)(x * c % mod); //代表r=0,那么xc就是第n个神奇数字long long l = x * c + 1, r = x * c + c;while (l < r) {long mid = (l + r) / 2;mid / a + mid / b - mid / c >= n ? r = mid : l = mid + 1;} return (int)(r % mod);} int lcm(int a, int b) {return a / gcd(a, b) * b;}int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}};
