容斥原理：求解《878. 第 N 个神奇数字》和《1201. 丑数 III》

将丑数的定义为能被 2 个数或 3 个数整除的数，用容斥原理求解《878. 第 N 个神奇数字》和《1201. 丑数 III》

丑数

能被 2 个数或 3 个数整除的数

• 无需记录每一步的丑数
• 指针，即倍数，直接相乘即可

模拟过程

输出能被 a b c 整除的第n个数 n 的范围扩大到 10<sup>9</sup>，超时

var nthUglyNumber = function(n, a, b, c) {
  const primes = [a, b, c], m = primes.length, p = [1, 1, 1]
  let r = 0
  for (let i = 0; i < n; i++) {
    let min = Number.MAX_SAFE_INTEGER, minIndexs = []
    for (let j = 0; j < m; j++) {
      const tmp = primes[j] * p[j]
      if (tmp < min) {
        min = tmp
        minIndexs = [j]
      } else if (tmp === min) {
        minIndexs.push(j)
      }
    }
    for (let j = 0; j < minIndexs.length; j++) p[minIndexs[j]]++
    r = min
  }
  return r
};

容斥原理

• 计算所有对象的数目
• 排除重复计算的数据

例题

878. 第 N 个神奇数字

一个正整数如果能被 a 或 b 整除，那么它是神奇的。 给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。

答案

var nthMagicalNumber = function(n, a, b) {
  const ab = lcm(a, b), MOD = 10 ** 9 + 7
  let l = 0, r = Math.min(a, b) * 10 ** 9
  while (l < r) {
    const m = Math.floor((l + r) / 2)
    const N = (m / a | 0) + (m / b | 0) - (m / ab | 0)
    if (N < n) l = (m + 1)
    else r = m
  }
  return l %  MOD
};
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b)
const lcm = (a, b) => a * b / gcd(a, b)

1201. 丑数 III

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。 丑数是可以被 a 或 b 或 c 整除的 正整数 。

答案

var nthUglyNumber = function(n, a, b, c) {
  const ab = lcm(a, b)
  const bc = lcm(b, c)
  const ac = lcm(a, c)
  const abc = lcm(ab, c)
  let l  = 0, r = Math.min(a, Math.min(b, c)) * 10 ** 9
  while (l < r) {
    const m = Math.floor((l + r) / 2)
    const N = (m / a | 0) + (m / b | 0) + (m / c | 0) - (m / ab | 0) - (m / ac | 0) - (m / bc | 0) + (m / abc | 0)
    if (N < n) l = m + 1
    else r = m
  }
  return l
};
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b)
const lcm = (a, b) => a * b / gcd(a, b)