数学与贪心

常用数学技巧

这一章不在主依赖链上

数学和贪心是两块游离的内容 —— 不依赖前面任何一章，也不被后面依赖。 随时可以插进来看，时间不够时也可以最后再看。

面试里真正会考的数学点不多，下面这几个基本就是全部。

埃氏筛：求 n 以内的所有素数

function sieve(n) {
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  for (let i = 2; i * i <= n; i++) {          // 🚨 外层到 √n 即可
    if (!isPrime[i]) continue;
    for (let j = i * i; j <= n; j += i) {     // 🚨 内层从 i² 开始
      isPrime[j] = false;
    }
  }

  return isPrime.reduce((acc, p, i) => (p ? (acc.push(i), acc) : acc), []);
}

⭐ 两个 i * i 各有各的道理，别记混：

  • 外层 i * i <= n：合数必有一个 ≤ √n 的因子，所以筛到 √n 就够了
  • 内层从 i * i 起：比 i² 小的 i 的倍数（2i, 3i, …） 一定已经被更小的素因子筛掉了

⚠️ 内层从 2 * i 开始也完全正确，只是多做无用功。 实测 n=100000：从 i² 起标记 193078 次，从 2i 起 202154 次 —— 只省 4.5%，远没有想象中夸张。

📌 所以这条优化的价值主要在「你能说清为什么」，而不是性能。

外层那个 i * i <= n 才是真的重要 —— 但它省的也不是标记次数：

n = 100000        外层轮数      标记次数
i * i <= n            315        193078
i <= n              99999        193078      ← 标记次数一模一样

⭐ 多出来的 99684 轮一次标记都没做（要么被 continue 掉， 要么 i² 已经大于 n，内层循环一次都不进）。 所以它省的是外层的空转，不是内层的工作量 —— 但外层轮数差了 317 倍。

gcd 与 lcm

欧几里得算法，三行：

const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
const lcm = (a, b) => (a / gcd(a, b)) * b;      // 🚨 先除再乘

🚨 lcm 里必须先除后乘。写成 a * b / gcd(a, b) 的话， a * b 这个中间值可能超过 Number.MAX_SAFE_INTEGER（2⁵³）而失精 —— 即使最终答案完全在安全范围内。

实测反例：

a = 521245998,  b = 286009542,  gcd = 365274
  a * b = 149081329157312930        （超过 2⁵³）

  先除后乘 (a/g)*b  →  408135616434          ✅ 精确
  先乘后除 a*b/g    →  408135616434.00006    ❌ 连整数都不是

⚠️ 注意错的那个不是差一点点，是直接变成了小数 —— 如果后面拿它去做取模或者当数组下标，会以很奇怪的方式炸掉， 而报错位置离真正的原因很远。

🚨 但这是个精心挑出来的反例，随机情况下它很少现形：

a、b 的量级      先乘后除的出错率
≤ 1e7                 0.00%
≤ 1e8                 0.02%
≤ 1e9                 4.2%

⭐ 二十万组 a, b ≤ 1e9 里只有 4.2% 出错（其中真变成小数的更少，只占 0.3%）。 所以这个 bug 属于「测一百组都碰不到、上线碰到一次就查半天」那一类 —— 不能靠随机测试发现，只能靠写的时候就写对。

⭐ 先除后乘的中间值只有 a/g，小得多，所以安全。 两种写法数学上完全等价，浮点数下不等价。

快速幂：O(log n) 而不是 O(n)

function power(base, exp, mod) {
  let res = 1;
  base %= mod;
  while (exp > 0) {
    if (exp & 1) res = (res * base) % mod;    // 当前位是 1 就乘进去
    base = (base * base) % mod;
    exp >>= 1;
  }
  return res;
}

思路：把指数拆成二进制。a¹³ = a⁸ · a⁴ · a¹， 底数每轮平方一次，指数每轮右移一位。

🚨 JavaScript 做模乘会失精 —— 这是真会踩的

上面那份代码有个 JS 特有的问题：res * base 可能超过 Number.MAX_SAFE_INTEGER（2⁵³）。

模数取常见的 1e9+7 时，两个乘数各自都接近 10⁹，乘积接近 10¹⁸ —— 远超 2⁵³ ≈ 9×10¹⁵。

实测：

(999999937 * 999999893) % 1000000007
  JS 算出   8023
  正确答案  7980        ← 差了 43

⚠️ 它不报错、不抛异常，就是安静地给一个错的数。 而且小数据完全正常，只有模数大到 10⁹ 量级才出问题。

⭐ JavaScript 的解法是用 BigInt：

function powerBig(base, exp, mod) {
  let res = 1n;
  base = BigInt(base) % BigInt(mod);
  const m = BigInt(mod);
  let e = BigInt(exp);
  while (e > 0n) {
    if (e & 1n) res = (res * base) % m;
    base = (base * base) % m;
    e >>= 1n;
  }
  return Number(res);
}

📌 什么时候需要换有个精确判据：mod² < 2⁵³， 即 mod < √(2⁵³) ≈ 9.5 × 10⁷。实测的拐点正好在这里：

mod        普通版出错率      mod²
1e5            0.00%        1.0e10
1e6            0.00%        1.0e12
1e7            0.00%        1.0e14
3e7            0.00%        9.0e14      ← 还在 2⁵³ 以内
1e8           13.93%        1.0e16      ← 越过 2⁵³ = 9.0e15
1e9+7         81.60%        1.0e18

🚨 而「代价是 BigInt 慢一个量级」这句话要反过来说。预热后各跑 2 万次：

mod = 1e9+7（中间值超 2⁵³）   Number 7.3ms   BigInt 3.0ms    BigInt 快 2.4×
mod = 9973 （中间值很小）      Number 0.5ms   BigInt 3.0ms    BigInt 慢 5.8×

⭐ 快慢在 2⁵³ 处反转。Number 版的中间值一旦超过 2⁵³ 就成了堆上的浮点对象， 每次乘法都要装箱；而 BigInt 在 64 位以内有快路径。

👉 结论：「BigInt 慢」只在你不需要它的时候成立。 真需要它（1e9+7 这种模数）的场合，它既更正确、又更快 —— 没有取舍。

⚠️ 量这个数一定要预热：不预热会量出「BigInt 更快」然后又在小模数上量出 「BigInt 慢 6 倍」，两次都对不上真实规律。

⚠️ Java / C++ 里对应的坑是 int 溢出，解法是转 long。 道理一样，只是阈值不同。

位运算：三个真的会考的

① n & (n - 1) 消掉最低位的 1

// 统计二进制里有几个 1
function countOnes(n) {
  let c = 0;
  while (n !== 0) { n &= n - 1; c++; }        // 每次消掉一个 1
  return c;
}

const isPowerOfTwo = (n) => n > 0 && (n & (n - 1)) === 0;   // 只有一个 1

原理：n - 1 会把最低位的 1 变成 0、它右边的 0 全变成 1， 再与一下，那一位就没了。

⭐ 循环次数等于 1 的个数，而不是 32 次 —— 稀疏的数上快得多。

② n & (-n) 取出最低位的 1

-n 是补码取反加一，所以 n & (-n) 恰好只留最低位那个 1。 树状数组全靠这一条。

③ 异或的两条性质

a ^ a = 0        自己和自己异或是 0
a ^ 0 = a        和 0 异或不变

于是「数组里只有一个数出现一次，其余都出现两次，找出它」一行就完了：

const singleNumber = (nums) => nums.reduce((a, b) => a ^ b, 0);

⚠️ JavaScript 的位运算会把操作数转成 32 位有符号整数。 所以 2**31 | 0 得到的是 -2147483648，而 2**32 | 0 是 0。

🚨 这直接波及上面那个一行解法：

singleNumber([2 ** 31, 5, 5])   // → -2147483648，正确答案是 2147483648

处理大于 2³¹ 的数时位运算不能直接用 —— 这一条在别的语言里没有对应物。 📌 算法题的取值范围通常压在 2³¹ 以内，所以碰不到；但这也意味着 你自测时也碰不到，写真实代码时要专门想一下。

下一步

贪心算法：什么时候「每步都选当下最好的」能得到全局最优， 以及一个只差一枚硬币的反例。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。

在本站 OJ 上练

这几道题在自己搭的判题机上，注册后直接提交，几秒出结果 —— 不用装环境、不用自己造测试数据。题目是自出的（无版权问题），每道题的数据都要求能抓出典型错解才准上线， 所以「样例过了」不等于能过。

  • P1007 判断素数判断单个素数（试除到 √n）—— 本篇埃氏筛的前置；边界是 n=1 和 n=2
  • P1016 分数化简辗转相除求 gcd，就是本篇「gcd 与 lcm」那一节