第N个神奇数字【LC878】
一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。
A positive integer is magical if it is divisible by either a or b.
Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.
好难好难
更新于2022/11/23
[为什么突然那么多人看 压力好大 那就快来把丑数系列都做了吧
如有错误 还请批评指正 ^ o ^]
找规律
首先是我自己的暴力思路，当然没通过…但是可以结合官方题解2找规律一起看看
- 思路：根据题意，我们需要找到第n个能被a或者b整除的数。暴力判断1~n*min(a,b)内有多少个神奇数，必然超时。
如何优化搜索的过程？神奇数一定是a或者b的倍数，因此只需判断a和b的整数倍即可。从小到大搜索第count个神奇数[过了50个还是超时]
。首先考虑几种特殊情况，a为b的因数或者b为a的因数，此时第n个神奇数即为 n * 较小值
。然后使用两个指针记录curA、curB，记录a的整数倍和b的整数倍，并使用count计数
- 如果curA < curB，那么第count个神奇数为curA，移动curA
- 如果curA < curB，那么第count个神奇数为curA，移动curB
- 如果curA == curB，那么第count个神奇数为curA即curB，curA和curB在该值重合，需同时移动curA和curB，count只计一次数
- 代码
class Solution { public int nthMagicalNumber(int n, int a, int b) { int MOD = (int)1e9 + 7; if (a == b){ return (int)((long)n * a % MOD); }else if (a % b == 0){ return (int)((long)n * b % MOD); }else if (b % a == 0){ return (int)((long)n * a % MOD); } long count = 0; long curA = a; long curB = b; long res = 0; while (count < n){ if (curA < curB){// 此时第count个神奇数字是curA count++; res = curA; curA += a; }else if (curA > curB){// 此时第count个神奇数字是curB count++; res = curB; curB += b; }else {// curA和curB重合，计数，并同时移动curA和curB count++; res = curB; curA += a; curB += b; } } return (int)(res % MOD); } }
。复杂度
- 时间复杂度：O ( n m） ，m为min(a,b)
- 空间复杂度：O ( 1 )
- 找规律，再次优化搜索过程。
。设f(x)为小于等于x的神奇数个数，c为a和b的最小公倍数，那么
。令小于等于c cc的神奇数个数m = f ( c )
。由于最终结果res一定是最小公倍数c的整数倍或者其的后几个数，因此r e s = c ∗ q + n u m
。因为不大于 c ∗ q 的「神奇数字」个数为m ∗ q ，所以我们只需要从 c ∗ q 往后搜第 r个「神奇数字」即可。
所以n可以由m表示，n = q ∗ m + r ,其中0 ≤ r < m ，q 为非负整数
- 如果r==0，那么c ∗ ( n / m )即为结果
- 如果r!=0，那么从res往后搜索r次即可
class Solution { static final int MOD = 1000000007; public 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 = (int) ((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 + Math.min(addA, addB) % MOD) % MOD; } public int lcm(int a, int b) { return a * b / gcd(a, b); } public int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/nth-magical-number/solutions/1983699/di-n-ge-shen-qi-shu-zi-by-leetcode-solut-6vyy/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O ( a + b )
- 空间复杂度：O ( 1 )
二分查找+数学
- 思路：将问题**“第n个神奇数是x”转化为“小于等于x的神奇数有n个”**，由于x越大n一定越大，因此可以使用二分法查找一个神奇数小于等于n的区间(0,right]，最后返回右边界
- 实现
。计算区间内的神奇数个数：假设该区间内能被a整除的数的个数为n a 个，能被b整除的数的个数为n b 个，能同时被a和被b整除的数的个数为n c 个，那么神奇数个数为n a + n b − n c
。na和nb 的计算方法较简单：除法运算向下取整即可
。n c =该区间内能被a和b的最小公倍数整除的个数
- 最小公倍数可以使用最小公约数gcd得到
- 最小公约数用辗转相除法得到
。实现
class Solution { private static final long MOD = (long) 1e9 + 7; public int nthMagicalNumber(int n, int a, int b) { long lcm = a / gcd(a, b) * b; long left = 0, right = (long) Math.max(a, b) * n; // 开区间 (left, right) while (left + 1 < right) { // 开区间不为空 long mid = left + (right - left) / 2; if (mid / a + mid / b - mid / lcm >= n)// 神奇数个数大于等于n right = mid; // 范围缩小到 (left, mid) else// 神奇数个数小于n left = mid; // 范围缩小到 (mid, right) } return (int) (right % MOD); } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/nth-magical-number/solutions/1984641/er-fen-da-an-rong-chi-yuan-li-by-endless-9j34/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O ( n l o g ( m ) ，m为min(a,b)
- 空间复杂度：O ( 1 )
