LeetCode-878. 第 N 个神奇数字【数学,二分查找,找规律】
题目描述:解题思路一:二分答案+容斥原理。给定一个上下界,然后依次增大下界或者减小上界,直到只剩一个答案。容斥原理是,加上两个集合,然后减去两个集合的交集。解题思路二:找规律解题思路三:0题目描述:
一个正整数如果能被 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 <= 10^9
2 <= a, b <= 4 * 10^4
/problems/nth-magical-number/description/
解题思路一:二分答案+容斥原理。给定一个上下界,然后依次增大下界或者减小上界,直到只剩一个答案。容斥原理是,加上两个集合,然后减去两个集合的交集。
class Solution {const long MOD =1e9+7;public:int nthMagicalNumber(int n, int a, int b) {long lcm=std::lcm(a,b);//最小公倍数long left=0,right=(long)min(a,b)*n;//开区间(left,right),在right情况下必有n个神奇数字。while(left+1<right){//开区间不为空long mid=left+(right-left)/2;if (mid/a+mid/b-mid/lcm>=n)//减去mid/lcm是a和b重复统计的个数right=mid;//范围缩小到(left,mid)else left=mid;//范围缩小到(mid,right)}return right%MOD;}};
时间复杂度:O(log(min(a,b)*n))
空间复杂度:O(1)
参考链接
解题思路二:找规律
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;}};
时间复杂度:O(a+b)
空间复杂度:O(1)
参考链接
解题思路三:0
如果觉得《LeetCode-878. 第 N 个神奇数字【数学 二分查找 找规律】》对你有帮助,请点赞、收藏,并留下你的观点哦!