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：= ret mod（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