---
title: "数学技巧"
created: 2025-12-22
---
# 数学技巧

### 一、 `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，不需要手写循环。

1. **十进制 转 其他进制 (返回 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进制）
   ```
2. **其他进制 转 十进制 (返回 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`。

```java
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
```

### 总结

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