数据结构
网络技术
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究C++ 中的第 N 个神奇数字
如果一个数字能被 A 或 B 整除，则称其为神奇数字。我们要找到第 N 个神奇数字。由于答案可能非常大，因此我们将以 10^9 + 7 为模返回它。
因此，如果输入是 N = 4，A = 4，B = 3，则输出将为 8
为了解决此问题，我们将遵循以下步骤 −
定义一个函数 cnt()，它将取 x、A、B，
返回 (x / A) + (x / B) - (x / A 和 B 的最小公倍数)
从主方法执行以下操作 −
l := 2，r := 1^14，ret := 0
while l <= r，执行 −
mid := l + (r - l) / 2
k := cnt(mid，A，B)
如果 k < N，则 −
l := mid + 1
否则 −
ret := mid
r := mid - 1
ret := ret 模 (10^9 + 7)
返回 ret
让我们看看以下实现以获得更好的理解 −
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
public:
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int lcm(int a, int b) { return (a * b) / gcd(a, b); }
lli cnt(lli x, lli A, lli B) {
return (x / A) + (x / B) - (x / lcm(A, B));
}
int nthMagicalNumber(int N, int A, int B) {
lli l = 2;
lli r = 1e14;
lli ret = 0;
while (l <= r) {
lli mid = l + (r - l) / 2;
lli k = cnt(mid, A, B);
if (k < N) {
l = mid + 1;
} else {
ret = mid;
r = mid - 1;
}
}
ret %= MOD;
return ret;
}
};
main(){
Solution ob;
cout << (ob.nthMagicalNumber(4, 4, 3));
}输入
4, 4, 3
输出
8
更新日期: 04-Jun-2020
187 次浏览
广告