C ++中的第N个幻数

  • Z时代
  • 2024-01-10
  • 分类：综合

如果数字可以被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

    以上是 C ++中的第N个幻数 的全部内容， 来源链接： utcz.com/z/316867.html

    回到顶部