点击知行合一Gesp>点击右上角“···”>设为星标🌟
大家好，我是黄老师。 曾任职多家国有大型科技公司，具有多年C/C++实战经验，打造过数百万用户规模的电子终端产品。目前是一名少儿C++编程业余讲师，毕竟CSP也自称非专业。😁
已经完成《GESP一级保命系列》专栏，《GESP二级编程保命-字符图形》专栏以及《GESP二级编程保命-暴力枚举》专栏、GESP三级编程-一维数组、GESP三级编程-字符串、GESP三级编程-进制转换、GESP三级编程-位运算、GESP三级编程-排序等等三级专题，供大家参考。
现在推出《GESP五级数论系列》专栏，并会分享相关实践经验，与同学们一起学习、进步。🚀
往期精选
GESP五级的核心就是“数据结构（链表）+ 基础算法（二分、贪心、分治、递归）+ 数论应用”。备考时，精力可以按 7:3 分配在“算法与数论”和“链表”上。考纲只要求链表，熟练掌握链表的选择、判断题目，满分是首要目标；初等数论与筛法：欧几里得算法、素数筛法、唯一分解定理等，务必掌握代码模版，灵活运用；四大核心算法包括贪心算法、二分算法、分治算法、递归算法！
质因数分解
五级
GESP 202309 因数分解
洛谷网B3871
↑微信扫码注册信奥公开课小程序↑
五级
题解思路
1. 题目分析
核心任务：
给定正整数 N（2 ≤ N ≤ 10¹²）
将 N 分解为质因数的乘积，按质因数从小到大输出
输出格式特殊要求：
质因数之间用
*分隔（星号左右各一个空格）若某个质因数出现多次（指数 > 1），用
^连接底数和指数（左右不空格）若指数为 1，不输出指数
样例验证：
N=6 → 2¹ × 3¹ → 输出
2 * 3✓N=20 → 2² × 5¹ → 输出
2^2 * 5✓N=23 → 23¹ → 输出
23✓
2. 建模思路
直接思路：模拟标准的质因数分解（唯一分解定理）
算法：试除法，从最小的质数 2 开始，不断除以当前质数，直到不能整除为止，记录每个质数的指数
当试除到 p 使得 p×p > N 时停止，若剩余 N > 1，则剩余部分是一个质数
数据范围分析：
N ≤ 10¹²，因此最多只需要试除到 √N ≤ 10⁶
循环次数最多 10⁶，完全可行（时间复杂度 O(√N)）
中间结果使用
long long类型（最大 10¹²，远小于 9.22×10¹⁸）
3. 算法选择
基础算法：试除法分解质因数
时间复杂度：O(√N) ≈ 10⁶ 次操作，可轻松通过
空间复杂度：O(1)（仅存储因子的临时变量）
优化：
单独处理因子 2 后，只试除奇数（减少一半循环）
但本题 N ≤ 10¹²，√N = 10⁶，即使不优化也很轻松
五级
试除枚举题解代码
试除枚举解法:
#include<bits/stdc++.h>using namespace std;intmain(){long long N;cin >> N;bool first = true; // 控制是否输出 "* "for (long long p = 2; p * p <= N; ++p) {if (N % p == 0) {int cnt = 0;while (N % p == 0) {N /= p;cnt++;}// 输出因子if (!first) cout << " * ";first = false;cout << p;if (cnt > 1) cout << "^" << cnt;}}// 如果剩余 N > 1，说明它是一个质因子（指数为1）if (N > 1) {if (!first) cout << " * ";cout << N;} cout << endl;return 0;}
↑微信扫码注册信奥公开课小程序↑
加 VX 联系年卡办理与备考资料领取
五级
STL题解参考
1、使用 std::map 存储因子和指数，自动排序
#include<bits/stdc++.h>using namespace std;intmain(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long N; cin >> N; map<long long, int> factors; // 自动按键（质因子）升序排列 for (long long p = 2; p * p <= N; ++p) { while (N % p == 0) { factors[p]++; N /= p; } } if (N > 1) factors[N]++; // 遍历 map 输出 bool first = true; for (auto &kv : factors) { if (!first) cout << " * "; first = false; cout << kv.first; if (kv.second > 1) cout << "^" << kv.second; } cout << endl; return 0;}
特点：
map 自动按质因子从小到大排序，省去手动维护顺序
代码更清晰，但多了对数级的插入开销（本题可忽略）
2、使用 vector<pair<long long, int>> 存储，手动排序
#include<bits/stdc++.h>using namespace std;intmain(){ ios::sync_with_stdio(false); cin.tie(0); long long N; cin >> N; vector<pair<long long, int>> factors; for (long long p = 2; p * p <= N; ++p) { if (N % p == 0) { int cnt = 0; while (N % p == 0) { N /= p; cnt++; } factors.emplace_back(p, cnt); } } if (N > 1) factors.emplace_back(N, 1); // factors 已经按 p 从小到大插入（循环递增），无需再排序 bool first = true; for (auto &pr : factors) { if (!first) cout << " * "; first = false; cout << pr.first; if (pr.second > 1) cout << "^" << pr.second; } cout << endl; return 0;}
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);long long N;cin >> N;map<long long, int> factors; // 自动按键（质因子）升序排列for (long long p = 2; p * p <= N; ++p) {while (N % p == 0) {factors[p]++;N /= p;}}if (N > 1) factors[N]++;// 遍历 map 输出bool first = true;for (auto &kv : factors) {if (!first) cout << " * ";first = false;cout << kv.first;if (kv.second > 1) cout << "^" << kv.second;}cout << endl;return 0;}
特点：
map自动按质因子从小到大排序，省去手动维护顺序代码更清晰，但多了对数级的插入开销（本题可忽略）
2、使用 vector<pair<long long, int>> 存储，手动排序
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(0);long long N;cin >> N;vector<pair<long long, int>> factors;for (long long p = 2; p * p <= N; ++p) {if (N % p == 0) {int cnt = 0;while (N % p == 0) {N /= p;cnt++;}factors.emplace_back(p, cnt);}}if (N > 1) factors.emplace_back(N, 1);// factors 已经按 p 从小到大插入（循环递增），无需再排序bool first = true;for (auto &pr : factors) {if (!first) cout << " * ";first = false;cout << pr.first;if (pr.second > 1) cout << "^" << pr.second;}cout << endl;return 0;}
特点：
使用
vector更轻量，适合已知顺序的情况适合需要后续随机访问的场景
3、使用 std::unordered_map 存储因子，再提取排序
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);long long N;cin >> N;unordered_map<long long, int> factors;for (long long p = 2; p * p <= N; ++p) {while (N % p == 0) {factors[p]++;N /= p;}}if (N > 1) factors[N]++;// unordered_map 无序，需要提取 key 排序vector<long long> primes;for (auto &kv : factors) primes.push_back(kv.first);sort(primes.begin(), primes.end());bool first = true;for (long long p : primes) {if (!first) cout << " * ";first = false;cout << p;if (factors[p] > 1) cout << "^" << factors[p];}cout << endl;return 0;}
特点：
哈希表查找 O(1)，适合因子数很多的情况（但本题因子数极少）
最后需要排序 keys，额外开销
4、使用 std::multiset 存储所有因子（包括重复），再统计
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);long long N;cin >> N;multiset<long long> ms; // 存储所有质因子（可重复）for (long long p = 2; p * p <= N; ++p) {while (N % p == 0) {ms.insert(p);N /= p;}}if (N > 1) ms.insert(N);// 遍历 multiset 统计每个质因子出现次数bool first = true;for (auto it = ms.begin(); it != ms.end(); ) {long long p = *it;int cnt = ms.count(p); // O(log n + cnt)if (!first) cout << " * ";first = false;cout << p;if (cnt > 1) cout << "^" << cnt;it = ms.upper_bound(p); // 跳到下一个不同元素}cout << endl;return 0;}
特点：
multiset自动排序，且允许重复用
count和upper_bound统计频次代码有趣但效率略低（因为有多次查找）
5、使用 std::stack 存储因子，反向输出（展示栈用法）
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);long long N;cin >> N;stack<pair<long long, int>> st; // 先存后出，可用来反转顺序for (long long p = 2; p * p <= N; ++p) {if (N % p == 0) {int cnt = 0;while (N % p == 0) {N /= p;cnt++;}st.push({p, cnt});}}if (N > 1) st.push({N, 1});// 由于我们是递增试除，但栈是后进先出，所以输出会从大到小// 但题目要求从小到大，所以这里先把栈元素倒入 vector 再反转输出vector<pair<long long, int>> vec;while (!st.empty()) {vec.push_back(st.top());st.pop();}reverse(vec.begin(), vec.end()); // 恢复从小到大bool first = true;for (auto &pr : vec) {if (!first) cout << " * ";first = false;cout << pr.first;if (pr.second > 1) cout << "^" << pr.second;}cout << endl;return 0;}
特点：
展示栈的 LIFO 特性，配合反转实现顺序输出
实际不推荐，但体现STL多样性
加 VX 联系年卡办理与备考资料领取
-= 扩展思考 =-
如果 N 扩大到 10¹⁸，√N = 10⁹，试除会超时。此时需要 Miller-Rabin 素性测试 + Pollard Rho 大数分解 算法，这属于高级数论内容。但本题 N ≤ 10¹²，试除法完全足够，体现了根据数据范围选择合适算法的能力。
