数学技巧

一、 `java.lang.Math` 常用函数速查

1. 基础运算

方法	描述	示例	注意事项
`Math.max(a, b)`	取最大值	`Math.max(10, 20)` -> `20`	支持 int, long, float, double
`Math.min(a, b)`	取最小值	`Math.min(10, 20)` -> `10`	同上
`Math.abs(a)`	取绝对值	`Math.abs(-5)` -> `5`	坑： `Math.abs(Integer.MIN_VALUE)` 仍然是负数（溢出）
`Math.pow(a, b)`	\(a^b\) (幂运算)	`Math.pow(2, 3)` -> `8.0`	返回 double，转 int 需要强转
`Math.sqrt(a)`	\(\\sqrt{a}\) (开方)	`Math.sqrt(9)` -> `3.0`	返回 double

2. 取整相关（重点）

方法	描述	示例	记忆口诀
`Math.ceil(a)`	向上取整	`3.1` -> `4.0`, `-3.1` -> `-3.0`	天花板 (Ceiling)
`Math.floor(a)`	向下取整	`3.9` -> `3.0`, `-3.1` -> `-4.0`	地板 (Floor)
`Math.round(a)`	四舍五入	`3.5` -> `4`, `3.4` -> `3`	原理是 `(long)Math.floor(a + 0.5d)`

3. 随机数

Math.random(): 返回 [0.0, 1.0) 之间的 double。
生成 [min, max] 之间的整数公式：
```
int randomNum = (int)(Math.random() * (max - min + 1)) + min;
```
建议：在算法题中通常使用 new Random().nextInt(n) 更方便。

必须掌握的“数学黑科技” (脱离 Math 库)

有些时候 Math 库因为处理的是 double，效率低且有精度问题。算法题中常用整数运算代替。

1. 整数向上取整 (Ceiling Division)

对于整数 \(a\) 除以 \(b\)，如果想要向上取整：

低效写法：(int)Math.ceil((double)a / b)
高效写法：(a + b - 1) / b

原理：

如果 a 能被 b 整除，a = k*b，则 (kb + b - 1) / b = k + (b-1)/b = k。正确。

如果 a 不能被 b 整除，a = k*b + r，则 (kb + r + b - 1) / b = k + (r+b-1)/b。因为 r>=1，分子足以凑出一个 1，结果为 k+1。正确。

2. 负数取模 (Modulus)

在 Java 中，% 运算符的结果符号跟随被除数。

-5 % 3 = -2 (而不是数学意义上的 1)

算法通用修正公式（保证结果为正数）：

// 计算 (a - b) % mod
int res = (a % mod + mod) % mod;

场景：环形数组下标移动、哈希表计算。

3. 快速幂 (Binary Exponentiation)

Math.pow(a, b) 处理大数取模时无法使用（因为 double 会丢失精度且无法中间取模）。

需要手写 \(O(\log k)\) 的快速幂：

// 计算 (a^k) % p
long qmi(long a, long k, long p) {
    long res = 1;
    while (k > 0) {
        if ((k & 1) == 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

4. 最大公约数 (GCD) 与最小公倍数 (LCM)

Java 没有内置 GCD 函数（直到 Java BigInteger），通常手写欧几里得算法：

// 递归版 GCD
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 最小公倍数 LCM
int lcm(int a, int b) {
    return (a * b) / gcd(a, b); // 注意 a*b 可能溢出，最好用 long
}

5. 判断质数与质数筛

试除法 (判断单个数，复杂度 \(O(\\sqrt{N})\))：

boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i++) { // i*i <= n 容易溢出，推荐 i <= n/i
        if (n % i == 0) return false;
    }
    return true;
}

三、进制转换技巧

Java 的 Integer 和 Long 类提供了极其强大的进制转换 API，不需要手写循环。

十进制转其他进制 (返回 String)

int n = 100;
String binary = Integer.toBinaryString(n); // 转二进制 "1100100"
String hex = Integer.toHexString(n);       // 转十六进制
String octal = Integer.toOctalString(n);   // 转八进制
String base7 = Integer.toString(n, 7);     // 转任意进制（例如7进制）

其他进制转十进制 (返回 int)

String s = "1100100";
int n = Integer.parseInt(s, 2); // 把二进制字符串转回 int
int m = Integer.parseInt("1A", 16); // 十六进制转 int

四、溢出处理与大数 (BigInteger)

1. 溢出陷阱

int 范围：\(\approx \pm 2 \times 10^9\)
long 范围：\(\approx \pm 9 \times 10^{18}\)

常见错误：

int a = 1000000000;
int b = 1000000000;
long c = a * b; // ❌ 错误！a*b 在赋值给 c 之前就已经以 int 类型计算并溢出了
long c = (long) a * b; // ✅ 正确

2. BigInteger

当数字超过 long 的范围（比如 100 位的数字），必须使用 java.math.BigInteger。

import java.math.BigInteger;

BigInteger a = new BigInteger("123456789123456789");
BigInteger b = BigInteger.valueOf(100); // 把 long 转为 BigInteger

// 运算不能用 +, -, *, /，必须用方法
BigInteger sum = a.add(b);
BigInteger sub = a.subtract(b);
BigInteger mul = a.multiply(b);
BigInteger div = a.divide(b);
BigInteger mod = a.mod(b);

// 比较
if (a.compareTo(b) > 0) { ... } // 相当于 a > b

总结

一般情况：用 Math.max, Math.min, Math.abs。
二分/分块：用 (a + b - 1) / b 代替 Math.ceil。
取模运算：涉及负数用 (a % mod + mod) % mod。
涉及乘法/累加：优先考虑 long 防止溢出。
超大数：用 BigInteger。