Question

878. Nth Magical Number

中文文档

Description

A positive integer is _magical_ if it is divisible by either a or b.

Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 1, a = 2, b = 3
Output: 2

Example 2:

Input: n = 4, a = 2, b = 3
Output: 6

 

Constraints:

• 1 <= n <= 109
• 2 <= a, b <= 4 * 104

Solutions

Solution 1

class Solution:
  def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
    mod = 10**9 + 7
    c = lcm(a, b)
    r = (a + b) * n
    return bisect_left(range(r), x=n, key=lambda x: x // a + x // b - x // c) % mod

class Solution {
  private static final int MOD = (int) 1e9 + 7;

  public int nthMagicalNumber(int n, int a, int b) {
    int c = a * b / gcd(a, b);
    long l = 0, r = (long) (a + b) * n;
    while (l < r) {
      long mid = l + r >>> 1;
      if (mid / a + mid / b - mid / c >= n) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return (int) (l % MOD);
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

using ll = long long;

class Solution {
public:
  const int mod = 1e9 + 7;

  int nthMagicalNumber(int n, int a, int b) {
    int c = lcm(a, b);
    ll l = 0, r = 1ll * (a + b) * n;
    while (l < r) {
      ll mid = l + r >> 1;
      if (mid / a + mid / b - mid / c >= n)
        r = mid;
      else
        l = mid + 1;
    }
    return l % mod;
  }
};

func nthMagicalNumber(n int, a int, b int) int {
  c := a * b / gcd(a, b)
  const mod int = 1e9 + 7
  r := (a + b) * n
  return sort.Search(r, func(x int) bool { return x/a+x/b-x/c >= n }) % mod
}

func gcd(a, b int) int {
  if b == 0 {
    return a
  }
  return gcd(b, a%b)
}