878.第N个神奇数字

链接：878.第N个神奇数字
难度：Hard
标签：数学、二分查找
简介：如果正整数可以被 A 或 B 整除，那么它是神奇的。

题解 1 - typescript

• 编辑时间：2021-12-11
• 执行用时：76ms
• 内存消耗：39.3MB
• 编程语言：typescript
• 解法介绍：求 1~n*min(a,b)中每一个数字，包括前面有的神奇数数量，用二分归为。

function gcd(a: bigint, b: bigint) {
  return b ? gcd(b, a % b) : a;
}
function lcm(a: bigint, b: bigint) {
  return (a * b) / gcd(a, b);
}
function f(x: bigint, a: bigint, b: bigint) {
  return x / a + x / b - x / lcm(a, b);
}
function nthMagicalNumber(n: number, a: number, b: number): number {
  let l = 1n;
  let r = BigInt(n * Math.min(a, b));
  const biga = BigInt(a);
  const bigb = BigInt(b);
  while (l < r) {
    const mid = (l + r) / 2n;
    const num = f(mid, biga, bigb);
    if (num >= n) r = mid;
    else l = mid + 1n;
  }
  return Number(l % BigInt(10 ** 9 + 7));
}

题解 2 - cpp

• 编辑时间：2022-11-22
• 执行用时：4ms
• 内存消耗：5.7MB
• 编程语言：cpp
• 解法介绍：二分，判断当前数是第几个数 = n / a + n / b - n / lcm。

class Solution {
public:
    const int mod = 1e9 + 7;
    int gcd(int a, int b) {
        if (b > a) return gcd(b, a);
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
    int nthMagicalNumber(int n, int a, int b) {
        long long l = min(a, b), r = n * l, m, nlcm = lcm(a, b);
        while (l < r) {
            m = (l + r) >> 1;
            int num = m / a + m / b - m / nlcm;
            if (num >= n) r = m;
            else l = m + 1;
        }
        return l % mod;
    }
};