这是一份为你整理的高中对数（Logarithm）基础知识梳理，从基本定义出发，逐步过渡到性质和经典例题，最后结合算法竞赛（ICPC/CCPC）中的实际应用进行分析。

---

### 一、 高中对数基础知识（由浅入深）

#### 1. 对数的定义与概念
对数是指数的逆运算。
如果 $a^x = N$ （其中底数 $a > 0$ 且 $a \neq 1$，真数 $N > 0$），那么数 $x$ 就叫做以 $a$ 为底 $N$ 的对数，记作：
$$\log\_a N = x$$

*   **底数限制**：$a > 0$ 且 $a \neq 1$（若 $a \le 0$ 或 $a=1$，指数函数无意义或为常数）。
*   **真数限制**：$N > 0$（在实数范围内，负数和零没有对数）。
*   **常用对数**：以 $10$ 为底的对数简记为 $\lg N$。
*   **自然对数**：以无理数 $e \approx 2.718$ 为底的对数简记为 $\ln N$。
*   **二进制对数**：以 $2$ 为底的对数记作 $\log\_2 N$（计算机科学中极常用）。

---

#### 2. 核心公式与运算性质
掌握对数的核心在于灵活运用以下公式。

##### ① 基本性质
*   $\log\_a 1 = 0$
*   $\log\_a a = 1$
*   **对数恒等式**：$a^{\log\_a N} = N$

##### ② 四则运算性质（同底数对数相加减）
*   **积的对数**：$\log\_a (M \cdot N) = \log\_a M + \log\_a N$
*   **商的对数**：$\log\_a \left(\frac{M}{N}\right) = \log\_a M - \log\_a N$
*   **幂的对数**：$\log\_a M^n = n \log\_a M$ （更通用地：$\log\_{a^m} b^n = \frac{n}{m} \log\_a b$）

##### ③ 换底公式（极重要）
换底公式用于将不同底数的对数转化到相同底数下：
$$\log\_a b = \frac{\log\_c b}{\log\_c a} \quad (c > 0 \text{ 且 } c \neq 1)$$

*   **常用推论**：
    *   **倒数关系**：$\log\_a b = \frac{1}{\log\_b a}$
    *   **链式乘法**：$\log\_a b \cdot \log\_b c = \log\_a c$

---

### 二、 经典数学例题

#### 例题 1：基础计算
**题目**：计算 $\log\_2 12 - \log\_2 3 + \log\_5 10 + \log\_5 2.5$ 的值。
**解析**：
1. 利用商的对数性质：$\log\_2 12 - \log\_2 3 = \log\_2 \left(\frac{12}{3}\right) = \log\_2 4 = \log\_2 2^2 = 2$。
2. 利用积的对数性质：$\log\_5 10 + \log\_5 2.5 = \log\_5 (10 \times 2.5) = \log\_5 25 = \log\_5 5^2 = 2$。
3. 两部分相加：$2 + 2 = 4$。
**答案**：$4$。

#### 例题 2：换底公式的应用
**题目**：已知 $\log\_3 2 = a$，用 $a$ 表示 $\log\_{12} 8$。
**解析**：
为了方便，我们把所有的对数通过换底公式统一化为以 $3$ 为底：
$$\log\_{12} 8 = \frac{\log\_3 8}{\log\_3 12}$$
将分子分母拆分：
*   分子：$\log\_3 8 = \log\_3 2^3 = 3 \log\_3 2 = 3a$
*   分母：$\log\_3 12 = \log\_3 (3 \times 4) = \log\_3 3 + \log\_3 2^2 = 1 + 2 \log\_3 2 = 1 + 2a$

因此，$\log\_{12} 8 = \frac{3a}{1 + 2a}$。

#### 例题 3：对数方程与定义域陷阱
**题目**：解方程 $\log\_2(x-1) + \log\_2(x+1) = 3$。
**解析**：
1.  **写出定义域限制（真数大于0）**：
    $$\begin{cases} x - 1 > 0 \\ x + 1 > 0 \end{cases} \implies x > 1$$
2.  **化简方程**：
    $$\log\_2[(x-1)(x+1)] = 3$$
    $$\log\_2(x^2 - 1) = 3$$
    $$x^2 - 1 = 2^3 = 8 \implies x^2 = 9$$
    解得 $x = 3$ 或 $x = -3$。
3.  **结合定义域检验**：
    因为 $x > 1$，所以舍去 $x = -3$。
**答案**：$x = 3$。

---

### 三、 算法竞赛（ICPC）中，通过 $\log$ 估算规模

在 ICPC 等算法竞赛中，我们主要关注**以 $2$ 为底的对数 $\log\_2$**。因为计算机内部是二进制，许多高效的数据结构和算法（如二分查找、线段树、倍增法、分治法）其规模缩减或树的深度都与 $2$ 的幂次紧密相关。

#### 1. 核心估算基准：$2^{10} \approx 10^3$
我们在估算时，最常用到的黄金等式是：
$$2^{10} = 1024 \approx 1000 = 10^3$$

由此我们可以推出以下估算规则（令 $\log$ 默认表示 $\log\_2$）：

| 指数关系 | 对应十进制规模 | 算法中的对数估算值 $\log\_2 N$ |
| :--- | :--- | :--- |
| $2^{10} \approx 10^3$ | 千 ($10^3$) | $\log\_2(10^3) \approx 10$ |
| $2^{20} \approx 10^6$ | 百万 ($10^6$) | $\log\_2(10^6) \approx 20$ |
| $2^{30} \approx 10^9$ | 十亿 ($10^9$) | $\log\_2(10^9) \approx 30$ |
| $2^{60} \approx 10^{18}$| $10^{18}$（C++中 `long long` 的极限） | $\log\_2(10^{18}) \approx 60$ |

---

#### 2. 估算在算法竞赛中的典型应用场景

##### 场景一：时间复杂度与运行时间估算
在 ICPC 中，标准 CPU 在 1 秒内大概可以执行 $10^8$ 次基本运算。我们需要通过数据规模 $N$ 来评估自己的算法是否会超时（TLE）。

*   **若 $N = 10^6$，算法复杂度为 $O(N \log N)$**：
    我们估算 $\log N \approx 20$（因为 $10^6 \approx 2^{20}$）。
    因此，运算次数大约为 $10^6 \times 20 = 2 \times 10^7$ 次。
    这明显小于 $10^8$，可以在 1 秒内稳稳地通过（常数不大时通常只需约 $0.05 \sim 0.1$ 秒）。
*   **若 $N = 10^5$，算法复杂度为 $O(N \log^2 N)$**：
    我们知道 $10^5$ 在 $10^3$ 和 $10^6$ 之间，由于 $2^{17} = 131072 \approx 1.3 \times 10^5$，可以估算 $\log N \approx 17$。
    运算次数大约为 $10^5 \times 17^2 = 10^5 \times 289 \approx 2.9 \times 10^7$ 次，仍然是非常安全的。

##### 场景二：二分查找（Binary Search）与三分查找的迭代次数
*   **整数二分**：
    若答案值域在 $[1, 10^9]$ 内，通过二分查找确定答案。每一次二分查找将区间减半，因此最多需要进行多少次循环？
    因为 $\log\_2(10^9) \approx 30$，所以最多只需要 **30次** 循环就能精确定位到唯一的整数答案。
*   **实数二分（浮点数二分）**：
    有时候我们需要在实数域 $[0, 10^9]$ 上求一个几何坐标或比例。由于浮点数存在精度限制，直接写 `while (r - l > eps)` 可能会因为精度问题陷入死循环。
    竞赛中常用的安全技巧是直接跑固定次数的循环：
    ```cpp
    for (int i = 0; i < 100; i++) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    ```
    为什么写 `100` 次循环绝对够？
    因为每次循环范围折半，100次后区间缩小了 $2^{-100}$ 倍。而 $2^{-100} = (2^{-10})^{10} \approx (10^{-3})^{10} = 10^{-30}$。
    这个精度已经远远超出了双精度浮点数 `double` 的有效精度极限（约 $10^{-15} \sim 10^{-16}$），可以保证精度绝对足够且不会死循环。

##### 场景三：空间复杂度与数组大小定义（以倍增法/ST表为例）
在求最近公共祖先（LCA）或使用 ST 表解决区间最值问题（RMQ）时，我们需要声明一个倍增数组 `fa[N][logN]`。
*   如果题目中节点数 $N \le 10^5$：
    因为 $2^{16} = 65536$ 还是比 $10^5$ 小，而 $2^{17} = 131072 > 10^5$。
    所以第二维的最大幂次设为 $17$ 即可，一般为了安全开到 $18$ 或 $20$。
    声明：`int fa[100005][18];`
*   如果题目中 $N \le 10^6$：
    因为 $2^{19} = 524288 < 10^6 < 2^{20} = 1048576$。
    所以第二维声明为 $20$ 或 $21$ 即可：
    声明：`int fa[1000005][21];`
    这样既保证空间不会浪费（防 MLE），也能确保不会越界。

一、高中对数基础知识（由浅入深）

1. 对数的定义与概念

对数是指数的逆运算。如果 $a^x = N$ （其中底数 $a > 0$ 且 $a \neq 1$，真数 $N > 0$），那么数 $x$ 就叫做以 $a$ 为底 $N$ 的对数，记作： $$\log_a N = x$$

底数限制：$a > 0$ 且 $a \neq 1$（若 $a \le 0$ 或 $a=1$，指数函数无意义或为常数）。
真数限制：$N > 0$（在实数范围内，负数和零没有对数）。
常用对数：以 $10$ 为底的对数简记为 $\lg N$。
自然对数：以无理数 $e \approx 2.718$ 为底的对数简记为 $\ln N$。
二进制对数：以 $2$ 为底的对数记作 $\log_2 N$（计算机科学中极常用）。

2. 核心公式与运算性质

掌握对数的核心在于灵活运用以下公式。

① 基本性质

$\log_a 1 = 0$
$\log_a a = 1$
对数恒等式：$a^{\log_a N} = N$

② 四则运算性质（同底数对数相加减）

积的对数：$\log_a (M \cdot N) = \log_a M + \log_a N$
商的对数：$\log_a \left(\frac{M}{N}\right) = \log_a M - \log_a N$
幂的对数：$\log_a M^n = n \log_a M$ （更通用地：$\log_{a^m} b^n = \frac{n}{m} \log_a b$）

③ 换底公式（极重要）

换底公式用于将不同底数的对数转化到相同底数下： $$\log_a b = \frac{\log_c b}{\log_c a} \quad (c > 0 \text{ 且 } c \neq 1)$$

常用推论：
- 倒数关系：$\log_a b = \frac{1}{\log_b a}$
- 链式乘法：$\log_a b \cdot \log_b c = \log_a c$

二、经典数学例题

例题 1：基础计算

题目：计算 $\log_2 12 - \log_2 3 + \log_5 10 + \log_5 2.5$ 的值。解析： 1. 利用商的对数性质：$\log_2 12 - \log_2 3 = \log_2 \left(\frac{12}{3}\right) = \log_2 4 = \log_2 2^2 = 2$。 2. 利用积的对数性质：$\log_5 10 + \log_5 2.5 = \log_5 (10 \times 2.5) = \log_5 25 = \log_5 5^2 = 2$。 3. 两部分相加：$2 + 2 = 4$。答案：$4$。

例题 2：换底公式的应用

题目：已知 $\log_3 2 = a$，用 $a$ 表示 $\log_{12} 8$。解析：为了方便，我们把所有的对数通过换底公式统一化为以 $3$ 为底： $$\log_{12} 8 = \frac{\log_3 8}{\log_3 12}$$ 将分子分母拆分： * 分子：$\log_3 8 = \log_3 2^3 = 3 \log_3 2 = 3a$ * 分母：$\log_3 12 = \log_3 (3 \times 4) = \log_3 3 + \log_3 2^2 = 1 + 2 \log_3 2 = 1 + 2a$

因此，$\log_{12} 8 = \frac{3a}{1 + 2a}$。

例题 3：对数方程与定义域陷阱

题目：解方程 $\log_2(x-1) + \log_2(x+1) = 3$。解析： 1. 写出定义域限制（真数大于0）： $$\begin{cases} x - 1 > 0 \ x + 1 > 0 \end{cases} \implies x > 1$$ 2. 化简方程： $$\log_2[(x-1)(x+1)] = 3$$ $$\log_2(x^2 - 1) = 3$$ $$x^2 - 1 = 2^3 = 8 \implies x^2 = 9$$ 解得 $x = 3$ 或 $x = -3$。 3. 结合定义域检验：因为 $x > 1$，所以舍去 $x = -3$。答案：$x = 3$。

三、算法竞赛（ICPC）中，通过 $\log$ 估算规模

在 ICPC 等算法竞赛中，我们主要关注以 $2$ 为底的对数 $\log_2$。因为计算机内部是二进制，许多高效的数据结构和算法（如二分查找、线段树、倍增法、分治法）其规模缩减或树的深度都与 $2$ 的幂次紧密相关。

1. 核心估算基准：$2^{10} \approx 10^3$

我们在估算时，最常用到的黄金等式是： $$2^{10} = 1024 \approx 1000 = 10^3$$

由此我们可以推出以下估算规则（令 $\log$ 默认表示 $\log_2$）：

指数关系	对应十进制规模	算法中的对数估算值 $\log_2 N$
$2^{10} \approx 10^3$	千 ($10^3$)	$\log_2(10^3) \approx 10$
$2^{20} \approx 10^6$	百万 ($10^6$)	$\log_2(10^6) \approx 20$
$2^{30} \approx 10^9$	十亿 ($10^9$)	$\log_2(10^9) \approx 30$
$2^{60} \approx 10^{18}$	$10^{18}$（C++中 `long long` 的极限）	$\log_2(10^{18}) \approx 60$

2. 估算在算法竞赛中的典型应用场景

场景一：时间复杂度与运行时间估算

在 ICPC 中，标准 CPU 在 1 秒内大概可以执行 $10^8$ 次基本运算。我们需要通过数据规模 $N$ 来评估自己的算法是否会超时（TLE）。

若 $N = 10^6$，算法复杂度为 $O(N \log N)$：我们估算 $\log N \approx 20$（因为 $10^6 \approx 2^{20}$）。因此，运算次数大约为 $10^6 \times 20 = 2 \times 10^7$ 次。这明显小于 $10^8$，可以在 1 秒内稳稳地通过（常数不大时通常只需约 $0.05 \sim 0.1$ 秒）。
若 $N = 10^5$，算法复杂度为 $O(N \log^2 N)$：我们知道 $10^5$ 在 $10^3$ 和 $10^6$ 之间，由于 $2^{17} = 131072 \approx 1.3 \times 10^5$，可以估算 $\log N \approx 17$。运算次数大约为 $10^5 \times 17^2 = 10^5 \times 289 \approx 2.9 \times 10^7$ 次，仍然是非常安全的。

场景二：二分查找（Binary Search）与三分查找的迭代次数

整数二分：若答案值域在 $[1, 10^9]$ 内，通过二分查找确定答案。每一次二分查找将区间减半，因此最多需要进行多少次循环？因为 $\log_2(10^9) \approx 30$，所以最多只需要 30次 循环就能精确定位到唯一的整数答案。
实数二分（浮点数二分）：有时候我们需要在实数域 $[0, 10^9]$ 上求一个几何坐标或比例。由于浮点数存在精度限制，直接写 while (r - l > eps) 可能会因为精度问题陷入死循环。竞赛中常用的安全技巧是直接跑固定次数的循环： cpp for (int i = 0; i < 100; i++) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } 为什么写 100 次循环绝对够？因为每次循环范围折半，100次后区间缩小了 $2^{-100}$ 倍。而 $2^{-100} = (2^{-10})^{10} \approx (10^{-3})^{10} = 10^{-30}$。这个精度已经远远超出了双精度浮点数 double 的有效精度极限（约 $10^{-15} \sim 10^{-16}$），可以保证精度绝对足够且不会死循环。

场景三：空间复杂度与数组大小定义（以倍增法/ST表为例）

在求最近公共祖先（LCA）或使用 ST 表解决区间最值问题（RMQ）时，我们需要声明一个倍增数组 fa[N][logN]。 * 如果题目中节点数 $N \le 10^5$：因为 $2^{16} = 65536$ 还是比 $10^5$ 小，而 $2^{17} = 131072 > 10^5$。所以第二维的最大幂次设为 $17$ 即可，一般为了安全开到 $18$ 或 $20$。声明：int fa[100005][18]; * 如果题目中 $N \le 10^6$：因为 $2^{19} = 524288 < 10^6 < 2^{20} = 1048576$。所以第二维声明为 $20$ 或 $21$ 即可：声明：int fa[1000005][21]; 这样既保证空间不会浪费（防 MLE），也能确保不会越界。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

log对数基础

一、 高中对数基础知识（由浅入深）