C ++中的第N个幻数
如果数字可以被A或B整除，则该数字被称为幻数。我们必须找到第N个幻数。由于答案可能非常大，我们将以10^9+7取模。
因此，如果输入为N=4，A=4，B=3，则输出将为8
为了解决这个问题，我们将遵循以下步骤-
定义一个函数cnt()，它将使用x，A，B，
返回（x/A）+（x/B）-（A和B的x/lcm）
从主要方法中，执行以下操作-
l：=2，r：=1^14，ret：=0
当l<=r时-
ret：=中
r：=中间-1
l：=中+1
中：=l+(r-l)/2
k：=cnt(mid,A,B)
如果k<N，则-
否则-
ret：=retmod（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