12954.因数分解

markdown
复制
1# 因数分解 题解
2
3## 题目分析
4
5本题要求将一个给定的正整数 $N$（$2 \le N \le 10^{12}$）分解为质因数的乘积，并按照规定的格式输出。格式要求如下：
6
7- 质因数按从小到大的顺序排列；
8- 乘号使用 `*`，且左右各有一个空格；
9- 当某个质因数出现多次时，写成指数形式，底数和指数之间用 `^` 连接，且左右不留空格。
10
11例如：
12- $6 = 2 * 3$
13- $20 = 2^2 * 5$
14
15本题本质上是考察质因数分解的基本算法，同时需要注意输出格式的细节。
16
17## 解题思路
18
191. **质因数分解**  
20   对于任意正整数 $N$，其大于 $\sqrt{N}$ 的质因数最多只有一个。因此我们可以从 $2$ 到 $\sqrt{N}$ 枚举可能的因子 $p$，只要 $p$ 能整除 $N$，就将 $p$ 作为质因数提取出来，并统计其出现次数，同时将 $N$ 不断除以 $p$。最后如果剩下的 $N > 1$，那么这个数就是最后一个质因数（且次数为 $1$）。
21
222. **输出格式控制**  
23   - 使用一个布尔变量 `first` 标记当前是否为第一个输出的因数。如果不是第一个，则在前面加上 ` * `。
24   - 先输出质因数本身，如果出现次数 `cnt > 1`，则紧跟着输出 `^` 和次数，中间没有空格。
25
26## 算法说明
27
28- **循环范围**：`p` 从 $2$ 开始，直到 `p * p <= n`。这是因为任何一个合数必然有一个质因子不超过其平方根。当 `n` 被除小后，循环的上界会动态减小，从而保证算法高效。
29- **统计次数**：当发现 `n % p == 0` 时，使用 `while` 循环不断将 `n` 除以 `p`，同时累加计数器。
30- **处理剩余的数**：循环结束后，如果 `n > 1`，说明这个 `n` 本身是一个大于 $\sqrt{N}$ 的质数，应将其作为最后一个因子输出。
31- **格式细节**：
32  - 乘号 `*` 左右各需一个空格，因此在每输出一个因子（第一个除外）前加 `" * "`。
33  - 指数符号 `^` 前后不加空格，因此直接拼接在底数后面。
34
35## 时间复杂度分析
36
37枚举的因子 `p` 最大到 $\sqrt{N}$，每次找到一个因子后都会将该因子除尽，因此实际遍历的 `p` 的次数约为 $O(\sqrt{N})$。由于 $N \le 10^{12}$，$\sqrt{N} \le 10^6$，在 1 秒的时间限制内完全可以通过。
38
39## 参考代码及解释
40
41```cpp
42#include <iostream>
43using namespace std;
44int main() {
45    long long N = 0;
46    cin >> N;
47    long long n = N;  // 保存原始值（可省略，此处仅用于说明）
48    bool first = true; // 标记是否为第一个因子
49    
50    // 从2开始试除，只需试到 sqrt(n)
51    for (long long p = 2; p * p <= n; p++) {
52        if (n % p != 0)
53            continue;      // 不是因子则跳过
54        int cnt = 0;
55        while (n % p == 0) {
56            cnt++;
57            n /= p;        // 不断除去因子p
58        }
59        // 控制乘号输出
60        if (!first) {
61            cout << " * ";
62        }
63        cout << p;         // 输出底数
64        if (cnt > 1)
65            cout << "^" << cnt; // 输出指数
66        first = false;
67    }
68    
69    // 若剩余的数大于1，说明是一个大于 sqrt(N) 的质因子
70    if (n > 1) {
71        if (!first) {
72            cout << " * ";
73        }
74        cout << n;
75    }
76    cout << endl;
77    return 0;
78}

代码说明：

1. long long n = N; 用 n 保存待分解的数，避免改变原始输入（本题中其实不需要保留，可直接使用 N，但保留也无妨）。
2. first 变量用于控制第一个因子的输出，之后每个因子前都会输出 *。
3. 循环内先判断 n % p == 0，再用 while 除尽该因子并统计次数。
4. 根据 cnt 决定是否输出指数形式。
5. 循环结束后处理可能剩下的大质数。

总结

本题是质因数分解的模板题。除了基本的分解算法外，重点在于按照题目要求的格式输出。需要特别注意乘号空格和指数格式的细节。类似问题在竞赛中很常见，掌握这一模板能够应对许多后续题目。