# 【GESP/CSP考点精讲】GESP五级 / CSP-J 必背：算术基本定理（唯一分解定理）与约数个数、约数和公式推导

> Author: OneCoder (李宏哲) | Canonical: https://www.coderli.com/gesp-5-knowledge-unique-factorization-divisors/
> Published: 2026-11-22 | Topic: GESP C++ 编程考级 / 五级
> Tags: GESP, CSP-J, C++, 考点精讲

在数论与计数类考题中，许多同学一看到“求 `360` 有多少个正约数、约数和是多少”或“把一个高达 $10^{12}$ 的整数拆成质因数乘积”，就陷入了两头踩坑的窘境：手写质因数分解代码时，枚举完 `i <= n / i` 后忘了补收尾的 `if (n > 1)`，结果在 `36` 上测试完美通过，一遇上 `12`、`84` 或任意大质数就漏掉最大的质因子，交上去喜提满屏 **WA**；背了约数个数公式 $(e_1 + 1)(e_2 + 1)\cdots(e_k + 1)$，却说不清为什么要给每个指数 `+1`，一旦初赛把问题改成“求 `360` 的**偶数**正约数个数”或“恰有 `4` 个正约数的数长什么样”，立刻凭感觉猜“奇偶各占一半”掉进出题人的陷阱；碰到经典的“1~n 盏灯开关问题”，还在写二重循环硬模拟，殊不知它背后藏着“完全平方数 ⟺ 约数个数为奇数”的秒杀规律！在 GESP 五级认证以及 CSP-J 初复赛中，**算术基本定理（唯一分解定理）的本质与 $O(\sqrt{n})$ 分解模板、由乘法原理推导约数个数与约数和公式、以及完全平方数拥有奇数个约数的核心推论**，是将数论与组合计数彻底打通的关键枢纽。本文将从底层逻辑与完整推导出发，把这套数论高频考点一次吃透。

## 🎯 考纲锚点与核心痛点

> 📍 **对应考点**：掌握算术基本定理（唯一分解定理）及 $O(\sqrt{n})$ 质因数分解代码模板，能基于分步乘法原理独立推导约数个数公式与约数和公式，熟练运用“完全平方数 ⟺ 约数个数为奇数”等核心推论。
> 🎯 **适用等级**：`GESP 五级考点 | CSP-J/S 初赛/复赛必考`

在历年 GESP 五级与 CSP-J 考场上，考生最常在以下三大痛点上丢分：
1. **“质因数分解漏写 `if (n > 1)`，被小样例迷惑”**：当 `n` 的所有质因子都不超过 $\sqrt{n}$（如 `36`）时，漏掉收尾判断也能侥幸算对；可一旦剩余的商本身是大质数（如 `12` 除完 `2^2` 剩 `3`、`84` 除完 `2^2 * 3` 剩 `7`），直接丢失最大质因子，导致分解式、约数个数与约数和全盘算错；
2. **“死记公式不解原理，遇变式就抓瞎”**：不理解约数个数与约数和背后的“质因子指数独立选法”与“乘法分配律逆用”，求偶数约数个数时误以为直接除以 `2`，或者忘记每个质因子都可以取 `0` 次方导致漏加 `+1`；
3. **“约数和不开 `long long` 或盲目套等比除法公式酿成溢出”**：哪怕 `n = 10^9` 还在 `int` 范围内，其约数和 $\sigma(10^9) = 2497558338$ 已超出 32 位有符号整数上限；若用等比求和公式 $\frac{p^{e+1}-1}{p-1}$ 计算大质数的约数和，中间项 $p^2$ 甚至直接撑爆 64 位 `long long`！

---

## 🧠 一、 核心原理深度拆解（有理论）

### 1. 算术基本定理（唯一分解定理）与 $O(\sqrt{n})$ 质因数分解

**算术基本定理（Fundamental Theorem of Arithmetic）**指出：任何一个**大于 `1` 的正整数 `n`**，都可以**唯一地**分解为有限个质数的乘积（不计质因数的排列顺序）。把相同的质因数合并成幂次，即可写成标准分解式：

$$n = p_1^{e_1} \cdot p_2^{e_2} \cdot \dots \cdot p_k^{e_k} \quad (p_1 < p_2 < \dots < p_k,\; e_i \ge 1)$$

> 🤔 **高频概念追问：为什么数学上严格规定 `1` 既不是质数，也不是合数？**
> 正是为了守护**唯一分解定理的“唯一性”**！假如把 `1` 当成质数，那么 `6` 就可以写成 $2 \times 3$、$1 \times 2 \times 3$、$1^2 \times 2 \times 3$、$1^{99} \times 2 \times 3$ 等无穷多种形式，唯一分解定理瞬间失效，整座初等数论大厦都会随之崩塌。

把唯一分解定理翻译成 C++11 代码，只需不到 15 行，但藏着**两大精妙的数学保证**：

```cpp
void factorize(long long n) {
    for (long long i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            int e = 0;
            while (n % i == 0) {
                n /= i;
                e++;
            }
            // 找到质因子 i，指数为 e
        }
    }
    if (n > 1) {
        // 剩下的 n 必是唯一大于 sqrt(原n) 的质因子，指数为 1
    }
}
```

1. **为什么 `i` 是逐一递增（`2, 3, 4, 5, 6, ...`），却绝不会把合数当成质因子输出？**
   反证法：假设某个合数 `c`（比如 `4` 或 `6`）能整除当前的 `n`。因为 `c` 是合数，它必有更小的质因数 `p < c`。但在循环走到 `c` 之前，早已路过 `p`，并且用 `while (n % p == 0) n /= p;` 把 `n` 体内所有的因子 `p` **彻底抽干**了！此时的 `n` 根本不再含因子 `p`，自然绝对不可能被 `c` 整除。因此，**任何进入 `if (n % i == 0)` 分支的 `i` 必为质数**！
2. **为什么循环条件只写 `i <= n / i`，最后再补一句 `if (n > 1)`？**
   **核心引理**：任意正整数 `n` **至多只包含 `1` 个大于 $\sqrt{n}$ 的质因数**。证明极其简短：倘若存在两个大于 $\sqrt{n}$ 的质因数 `p` 和 `q`，则它们的乘积满足 $p \cdot q > \sqrt{n} \cdot \sqrt{n} = n$，与“二者皆为 `n` 的因子”矛盾！
   因此，当所有不超过 $\sqrt{n}$ 的小质因数都被除尽后，剩下的 `n` 只剩两种结局：要么缩成 `1`（分解完毕），要么本身就是那唯一剩下的大质因数（指数必为 `1`）。而且每次除尽因子后 `n` 实时变小，循环上界 `n / i` 动态收紧，最坏情况（`n` 本身是质数）仅运行 $\lfloor\sqrt{n}\rfloor$ 步，时间复杂度严格为 **$O(\sqrt{n})$**，同时用 `i <= n / i` 彻底消灭了 `i * i` 溢出风险。

---

### 2. 基于乘法原理推导约数个数公式 $d(n)$

设正整数的标准质因数分解为 $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$。由唯一分解定理可知，正整数 `d` 能整除 `n`，**当且仅当** `d` 不包含 `n` 以外的新质因子，且每个质因子的幂次都不超过 `n` 中对应的幂次：

$$d = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \quad (0 \le a_i \le e_i)$$

因此，构造一个正约数 `d` 等价于完成 `k` 步彼此独立的决策：
* 决定质因子 $p_1$ 取几个：$a_1 \in \{0, 1, 2, \dots, e_1\}$，共有 **`e1 + 1`** 种选法（**别忘了 `a1 = 0` 代表“不选 $p_1$”**）；
* 决定质因子 $p_2$ 取几个：$a_2 \in \{0, 1, 2, \dots, e_2\}$，共有 **`e2 + 1`** 种选法；
* ……
* 决定质因子 $p_k$ 取几个：$a_k \in \{0, 1, 2, \dots, e_k\}$，共有 **`ek + 1`** 种选法。

根据**分步乘法计数原理**，正约数总个数 $d(n)$ 等于各质因子指数加 `1` 后的连乘积：

$$d(n) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1) = \prod_{i=1}^{k} (e_i + 1)$$

以 `n = 72 = 2^3 × 3^2` 为例，质因子 `2` 有 `3 + 1 = 4` 种选法，质因子 `3` 有 `2 + 1 = 3` 种选法，它们像棋盘的横纵坐标一样两两配对，不重不漏地生成全部 **`4 × 3 = 12`** 个正约数：

```text
========================================================================
【72 = 2^3 × 3^2 的全部正约数生成矩阵（4 行 × 3 列 = 12 个约数）】

          │    3^0 (= 1)     │    3^1 (= 3)     │    3^2 (= 9)
──────────┼──────────────────┼──────────────────┼──────────────────
2^0 (= 1) │  1 × 1 =   1     │  1 × 3 =   3     │  1 × 9 =   9
2^1 (= 2) │  2 × 1 =   2     │  2 × 3 =   6     │  2 × 9 =  18
2^2 (= 4) │  4 × 1 =   4     │  4 × 3 =  12     │  4 × 9 =  36
2^3 (= 8) │  8 × 1 =   8     │  8 × 3 =  24     │  8 × 9 =  72
──────────┴──────────────────┴──────────────────┴──────────────────
  ▶ 约数个数：行数(3+1) × 列数(2+1) = 4 × 3 = 12
  ▶ 约数之和：(1 + 2 + 4 + 8) × (1 + 3 + 9) = 15 × 13 = 195
========================================================================
```

---

### 3. 乘法分配律逆用：推导约数和公式 $\sigma(n)$

盯着上面的 `4 × 3` 约数矩阵，如果把这 `12` 个数全部加起来，完全不需要一个个硬算！利用初中就学过的**乘法分配律逆用**，先把每一行的公因子提出来，再提公共括号：

$$\sigma(72) = (2^0 + 2^1 + 2^2 + 2^3) \times (3^0 + 3^1 + 3^2) = 15 \times 13 = 195$$

把连乘积展开后的每一项，恰好唯一对应 `n` 的一个正约数 $p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$，**既无重复，也无遗漏**！由此立刻得到一般形式的**约数和公式**：

$$\sigma(n) = \prod_{i=1}^{k} \left(1 + p_i + p_i^2 + \dots + p_i^{e_i}\right) = \prod_{i=1}^{k} \frac{p_i^{e_i + 1} - 1}{p_i - 1}$$

#### 代码实现神技：秦九韶迭代累加 `sub_sum = sub_sum * p + 1`

在程序中计算括号内的等比数列和 $1 + p + p^2 + \dots + p^e$ 时，**千万不要**套右侧的除法公式 $\frac{p^{e+1}-1}{p-1}$！直接初始化 `sub_sum = 1`，在 `while (n % i == 0)` 每次除以 `i` 的同时执行一行 **`sub_sum = sub_sum * i + 1;`** 即可：
* 除第 `1` 次：`1 * p + 1 = p + 1`
* 除第 `2` 次：`(p + 1) * p + 1 = p^2 + p + 1`
* 除第 `e` 次：$p^e + \dots + p + 1$

这种写法**不需要多算 $p^{e+1}$（防溢出）、不需要做除法（遇取模题无需模逆元）**，仅需一行代码就与质因数分解无缝融合！

---

### 4. 高频神级推论：完全平方数 ⟺ 约数个数为奇数

在 GESP 和 CSP-J 初赛中，常考这样一类脑筋急转弯：“一个正整数什么时候会有**奇数个**正约数？”

我们用约数个数公式一击秒杀：
* 乘积 $d(n) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1)$ 是**奇数**；
* ⟺ 每一个乘数 $(e_i + 1)$ 全部都是**奇数**（只要有一个偶数，乘积立马变偶数）；
* ⟺ 所有质因子的指数 $e_1, e_2, \dots, e_k$ 全部都是**偶数**（可记作 $e_i = 2m_i$）；
* ⟺ $n = p_1^{2m_1} p_2^{2m_2} \cdots p_k^{2m_k} = \left(p_1^{m_1} p_2^{m_2} \cdots p_k^{m_k}\right)^2$，即 **`n` 必定是一个完全平方数**！

从直觉上理解同样优美：正约数总是以 $(a, n / a)$ 成双成对出现，只有当 `n` 是完全平方数时，正中间会冒出一个“自己和自己配对”的约数 $a = n / a = \sqrt{n}$，导致总约数个数多出孤零零的 `1` 个而变成奇数。

| 核心考点 / 结论 | 数学表达式 | 典型应用场景与秒杀技巧 |
| :---: | :--- | :--- |
| **唯一分解定理** | $n = \prod_{i=1}^{k} p_i^{e_i}$ | 求 GCD（各质因子指数取 $\min$）、求 LCM（各质因子指数取 $\max$） |
| **约数个数公式** | $d(n) = \prod_{i=1}^{k} (e_i + 1)$ | 统计约数总数、限定条件约数个数（如偶数约数、某个数的倍数约数） |
| **约数和公式** | $\sigma(n) = \prod_{i=1}^{k} (1 + p_i + \dots + p_i^{e_i})$ | 完美数判定（$\sigma(n) = 2n$）、亲和数判定、大数约数和取模 |
| **奇偶性推论** | $d(n)$ 为奇数 $\iff n = m^2$ | 经典“1~n 盏开关灯问题”：最终亮着的灯正是 `1..n` 中的完全平方数，共 $\lfloor\sqrt{n}\rfloor$ 盏 |

> 💡 **考场黄金法则**：
> 1. **【分解三件套：`i <= n / i` + `while` 除尽 + `if (n > 1)` 收尾】**：三者缺一不可，时间复杂度严格 $O(\sqrt{n})$ 且永不溢出、绝不漏大质因子。
> 2. **【约数计数抓“指数选法”，约数求和用 `sub = sub * p + 1`】**：把每个质因子看成独立维度（指数 `+1` 包含 `0` 次方），牢记完全平方数的所有质因子指数全为偶数、恰有奇数个正约数！

---

## 🔍 二、 具象代码与数据推演（有举例）

### 示例：追踪 `n = 84` 的质因数分解、动态缩界与收尾捕获

下面这段 26 行的标准 C++11 程序对 `n = 84`（$84 = 2^2 \times 3^1 \times 7^1$）一站式完成质因数分解、约数个数与约数和计算，并实时打印每一步的内存状态变化：

```cpp
#include <iostream>
using namespace std;

int main() {
    long long n = 84;
    long long div_cnt = 1, div_sum = 1;
    cout << "Start: n=" << n << endl;
    for (long long i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            int e = 0;
            long long sub_sum = 1;
            while (n % i == 0) {
                n /= i;
                e++;
                sub_sum = sub_sum * i + 1;
            }
            div_cnt *= (e + 1);
            div_sum *= sub_sum;
            cout << "Factor " << i << "^" << e
                 << " -> rem n=" << n
                 << ", cnt=" << div_cnt
                 << ", sum=" << div_sum << endl;
        }
    }
    if (n > 1) {
        div_cnt *= 2;
        div_sum *= (1 + n);
        cout << "Tail   " << n << "^1"
             << " -> rem n=1"
             << ", cnt=" << div_cnt
             << ", sum=" << div_sum << endl;
    }
    return 0;
}
```

#### 分步内存变量变化与循环缩界推演表

| 阶段 / 循环变量 `i` | 进入前剩余 `n` | 上界判据 `i <= n / i` | 内层 `while` 除尽与 `sub_sum` 变化 | 更新后 `div_cnt` | 更新后 `div_sum` |
| :---: | :---: | :---: | :--- | :---: | :---: |
| **初始状态** | `84` | — | — | `1` | `1` |
| **`i = 2`** | `84` | `2 <= 42`（真） | `84 -> 42 -> 21`（`e = 2`），`sub_sum: 1 -> 3 -> 7` | `1 * 3 = 3` | `1 * 7 = 7` |
| **`i = 3`** | `21` | `3 <= 7`（真） | `21 -> 7`（`e = 1`），`sub_sum: 1 -> 4` | `3 * 2 = 6` | `7 * 4 = 28` |
| **`i = 4`** | `7` | `4 <= 1`（**假！提前结束**） | 退出 `for` 循环（注意 `i` 根本没跑到 `7`！） | `6` | `28` |
| **收尾 `if (n > 1)`** | `7` | `7 > 1`（真） | 捕获残余大质因子 **`7^1`**，`1 + 7 = 8` | `6 * 2 = 12` | `28 * 8 = 224` |

手算全部正约数核对：`84` 的全部 `12` 个正约数为 `1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84`，首尾配对求和 `(1+84)+(2+42)+(3+28)+(4+21)+(6+14)+(7+12) = 85+44+31+25+20+19 = 224`，完全吻合！

程序经 `g++ -O2 -std=c++11` 编译运行实际输出：

```text
Start: n=84
Factor 2^2 -> rem n=21, cnt=3, sum=7
Factor 3^1 -> rem n=7, cnt=6, sum=28
Tail   7^1 -> rem n=1, cnt=12, sum=224
```

---

## ⚡ 三、 考场高频避坑指南（正误辨析）

在 GESP 五级判断题与 CSP-J 考场上，以下三个边界陷阱最容易让人痛失满分：

### ❌ 易错点 1：漏写循环后的收尾判断 `if (n > 1)`，被 `36` 这类样例麻痹！
* **错误代码**：
  ```cpp
  for (long long i = 2; i <= n / i; i++) {
      if (n % i == 0) {
          int e = 0;
          while (n % i == 0) { n /= i; e++; }
          div_cnt *= (e + 1);
      }
  }
  // 致命漏写：缺少 if (n > 1) div_cnt *= 2;
  ```
* **为什么错**：这段错代码极具欺骗性——测 `n = 36` 时，`i = 2` 把 `36` 除成 `9`，`i = 3` 恰好满足 `3 <= 9 / 3` 把 `9` 除成 `1`，输出 `div_cnt = 9` 竟然**全对**！但只要换一个极小的合数 `n = 12`：`i = 2` 把 `12` 除成 `3`，下一轮 `i = 3` 检查条件 `3 <= 3 / 3 = 1` 直接为**假**并跳出循环，剩下的质因子 `3` 被彻底丢弃，错算出 `d(12) = 3`（正解为 `6`）；对任意质数（如 `7`、`13`），更会直接错算出 `d(p) = 1`！
* **正确规范**：质因数分解的 `for` 循环一结束，条件反射式地紧跟 **`if (n > 1)`**，把残余的大质因子以指数 `1` 纳入统计（约数个数乘 `2`，约数和乘 `1 + n`）。

### ❌ 易错点 2：把 `1` 当作质数处理，或忘加 `+1` 混淆“指数乘积”与“约数个数”！
* **错误认知**：认为 `n = 2^3 × 3^2` 的约数个数是 `3 × 2 = 6`；或者在特判 `n = 1` 时把它输出为质因子 `1^1`，甚至误认为 `d(1) = 0`。
* **为什么错**：
  1. 对 $n = p_1^{e_1} \cdots p_k^{e_k}$，每个质因子并非至少选 `1` 个，而是**允许选 `0` 个**（当所有质因子都选 `0` 个时，拼出的正是约数 `1`），因此可选方案数是 `(e_i + 1)` 而非 `e_i`；
  2. `1` 没有任何质因子（空乘积），它唯一的正约数就是自身 `1`，所以 `d(1) = 1`、`sigma(1) = 1`——好在我们的代码初始化 `div_cnt = 1, div_sum = 1`，当 `n = 1` 时循环和 `if (n > 1)` 均不进入，天然正确得出 `1` 和 `1`（仅在打印分解式时需特判输出 `1`）。
* **正确规范**：牢记公式里每一项必须 **`+1`**，且 **`1` 不是质数也不是合数**。

### ❌ 易错点 3：约数和仍用 `int` 存储，或硬套等比除法公式 `(p^(e+1) - 1) / (p - 1)` 导致溢出！
* **错误写法**：题目给的 `n` 不超过 $10^9$（放得进 `int`），便顺手声明 `int div_sum = 1;`，或者写 `(pow(p, e + 1) - 1) / (p - 1)` 求单组质因子的幂次和。
* **为什么错**：
  1. **约数和远超 `n` 本身**：实测 `n = 1000000000`（$10^9$，完全在 `int` 范围内）的正约数和高达 **`2497558338`**，直接撑爆 32 位 `int` 上限 `2147483647` 变成负数；甚至质数 `n = 2147483647` 的约数和 `2147483648` 也会刚好爆 `int`！
  2. **等比公式的分子 $p^{e+1}$ 爆炸与浮点精度坑**：`pow()` 返回 `double`，超过 $2^{53}$ 会直接丢精度；即便手写整数快速幂算 $p^{e+1}$，当 `n` 是接近 $10^{10}$ 的大质数（`e = 1`）时，分子 $p^2 - 1 \approx 10^{20}$ 直接冲破 `long long` 上限 $9.22 \times 10^{18}$！
* **正确规范**：统计约数个数与约数和一律使用 **`long long`**，并用纯整数迭代 **`sub_sum = sub_sum * i + 1`** 累加每组等比和，彻底远离 `pow()`、中间大幂次溢出与除法取模难题。

---

## 📝 四、 真题实战演练与精析（有例题：3 道）

### 【例题 1 · 单选题】（GESP 五级 / CSP-J 初赛高频计算与变式考点：约数个数、偶数约数与约数和综合秒算）

**题目**：正整数 `360` 共有多少个正约数？其中**偶数正约数**有多少个？所有正约数的和是多少？（ ）

* **A.** `24` 个、`12` 个、`1170`
* **B.** `24` 个、`18` 个、`1170`
* **C.** `24` 个、`18` 个、`1080`
* **D.** `18` 个、`12` 个、`1170`

**🔍 答案与逐项排除解析**：
* **正确答案**：**B**
* **解析过程**：
  1. **标准质因数分解**：$360 = 36 \times 10 = (2^2 \times 3^2) \times (2 \times 5) = 2^3 \times 3^2 \times 5^1$。
  2. **求正约数总个数（排除 D）**：套用乘法原理公式：
     $$d(360) = (3 + 1) \times (2 + 1) \times (1 + 1) = 4 \times 3 \times 2 = 24$$
     直接排除 D。
  3. **求偶数正约数个数（排除 A 的头号陷阱！）**：很多同学凭直觉误以为“约数里奇数、偶数各占一半，所以 `24 / 2 = 12`”，于是中计错选 A！
     正确做法是回到**质因子指数选法**：一个约数是偶数，**当且仅当它至少包含一个质因子 `2`**，即 `2` 的指数 $a_1$ 只能从 $\{1, 2, 3\}$ 里选（**`3` 种选法**，踢掉 $a_1 = 0$），而 `3` 仍有 `2 + 1 = 3` 种选法、`5` 仍有 `1 + 1 = 2` 种选法。因此偶数约数个数为：
     $$3 \times 3 \times 2 = 18$$
     （也可以用补集思维验证：奇数约数不含因子 `2`，个数为 $(2 + 1)(1 + 1) = 6$，故偶数约数为 `24 - 6 = 18`！）由此秒杀排除 A。
  4. **求全部正约数之和（排除 C）**：套用约数和公式：
     $$\sigma(360) = (1 + 2 + 4 + 8) \times (1 + 3 + 9) \times (1 + 5) = 15 \times 13 \times 6 = 1170$$
     排除 C，稳稳锁定 **B**。

---

### 【例题 2 · 判断题】（GESP 五级数论推论逆向辨析：恰有 `4` 个正约数的数长什么样？）

**题目**：如果一个正整数 `n` 恰有 `4` 个正约数，那么 `n` 必然可以表示为两个**不同质数**的乘积（即形如 $n = p \times q$，其中 `p` 与 `q` 为不相等的质数）。（ ）

**🔍 答案与反例证明**：
* **结论**：**错误（×）**
* **辨析证明**：
  1. **逆推公式拆分漏了情况**：由约数个数公式 $d(n) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1) = 4$（其中每个括号都满足 $e_i + 1 \ge 2$），把整数 `4` 拆成不小于 `2` 的正整数乘积，共有**两种**合法拆法：
     * **情况一**：$4 = 2 \times 2 = (1 + 1)(1 + 1)$，对应两个不同质数的一次幂相乘，即 $n = p_1^1 \cdot p_2^1$（例如 `6 = 2 × 3`、`10 = 2 × 5`）；
     * **情况二**：$4 = 4 = (3 + 1)$，对应**单个质数的三次方**，即 $n = p^3$！
  2. **极简反例**：取 **`n = 8 = 2^3`**（或 `27 = 3^3`、`125 = 5^3`）。`8` 的全部正约数为 `1, 2, 4, 8`，恰有 **`4`** 个正约数，但 `8` 只有唯一的质因子 `2`，根本无法写成两个不同质数的乘积！因此原命题错误。

---

### 【例题 3 · 微代码实战】（GESP 五级 / CSP-J 复赛高频母题：多组大整数质因数分解、约数个数与约数和一站式统计）

**题目描述**：给定 `T`（$1 \le T \le 100$）组测试数据，每组给出一个正整数 `n`（$1 \le n \le 10^{12}$）。请对每个 `n` 输出两行结果：
* 第一行：按质因数从小到大的顺序输出 `n` 的标准质因数分解式，每个质因子写作 `p^e`（若指数 `e == 1` 则简写为 `p`），相邻项用 ` * ` 连接；特别地，若 `n == 1`，第一行直接输出 `1`；
* 第二行：输出两个用空格隔开的整数，依次为 `n` 的**正约数个数** $d(n)$ 与**正约数之和** $\sigma(n)$。

**输入格式**：
第一行包含一个正整数 `T`，表示测试数据组数。
接下来 `T` 行，每行包含一个正整数 `n`。

**输出格式**：
对于每组数据，输出两行：第一行为标准质因数分解式，第二行为正约数个数和正约数之和。

**💡 算法建模与关键细节**：
1. **数据范围与防溢出**：`n` 最高达 $10^{12}$，必须使用 `long long` 读入并计算；循环上限 `i <= rem / i` 最多枚举到 $10^6$，单组数据最坏 $O(\sqrt{n}) \approx 10^6$ 次运算，`T <= 100` 总计不超过 $10^8$ 步，远在 1 秒时限内轻松通过；
2. **迭代求约数和**：内层 `while` 每除一次 `i`，顺手执行 `sub_sum = sub_sum * i + 1`，全程不产生大于 $2n$ 的中间值，在 $n \le 10^{12}$ 下总约数和 $\sigma(n)$ 远小于 $10^{13}$，在 `long long` 中绝对安全；
3. **特判 `n == 1` 与收尾 `if (rem > 1)`**：先特判 `n == 1` 输出 `1` 与 `1 1`；对 `n >= 2`，循环结束后务必判断 `rem > 1`，把可能残留的大质因子按指数 `1` 拼入分解式，并将 `div_cnt *= 2`、`div_sum *= (1 + rem)`。

```cpp
#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        long long n;
        cin >> n;
        if (n == 1) {
            cout << "1\n1 1\n";
            continue;
        }
        long long rem = n;
        long long div_cnt = 1;
        long long div_sum = 1;
        bool first = true;

        for (long long i = 2; i <= rem / i; i++) {
            if (rem % i == 0) {
                int e = 0;
                long long sub_sum = 1;
                while (rem % i == 0) {
                    rem /= i;
                    e++;
                    sub_sum = sub_sum * i + 1;
                }
                if (!first) cout << " * ";
                first = false;
                cout << i;
                if (e > 1) cout << "^" << e;
                div_cnt *= (e + 1);
                div_sum *= sub_sum;
            }
        }
        if (rem > 1) {
            if (!first) cout << " * ";
            cout << rem;
            div_cnt *= 2;
            div_sum *= (1 + rem);
        }
        cout << "\n" << div_cnt << " " << div_sum << "\n";
    }
    return 0;
}
```

* **输入样例**：
  ```text
  5
  1
  36
  84
  360
  999999999989
  ```
* **输出样例**：
  ```text
  1
  1 1
  2^2 * 3^2
  9 91
  2^2 * 3 * 7
  12 224
  2^3 * 3^2 * 5
  24 1170
  999999999989
  2 999999999990
  ```
  *（样例解释：`1` 特判输出 `1` 与 `1 1`；`36 = 2^2 * 3^2` 是完全平方数，指数全为偶数，恰有奇数个约数 `9` 个，约数和 `(1+2+4)*(1+3+9) = 91`；`84` 与 `360` 分别验证了收尾大质因子捕获与多质因子连乘；`999999999989` 是接近 $10^{12}$ 的大质数，循环结束后由 `if (rem > 1)` 捕获，迅速得出 `2` 个约数且约数和 `999999999990` 无溢出。）*

---
Source: OneCoder (https://www.coderli.com/gesp-5-knowledge-unique-factorization-divisors/) | GESP Wiki: https://wiki.coderli.com/ | OI-Game: https://oi.coderli.com/
