【GESP】C++ 五级真题解析，[2025年12月，第十二次认证]第二题-相等序列 luogu-p14918
GESP C++ 2025年12月，五级真题第二题，考察数论与贪心算法思想，对考试来说有一定难度。题目难度⭐⭐⭐☆☆。洛谷难度等级普及/提高−。
P14918 [GESP202512 五级] 相等序列
题目要求
题目描述
小 A 有一个包含 $N$ 个正整数的序列 $A={A_1,A_2,\ldots,A_N}$。小 A 每次可以花费 $1$ 个金币执行以下任意一种操作：
- 选择序列中一个正整数 $A_i$（$1\le i\le N$），将 $A_i$ 变为 $A_i\times P$，$P$ 为任意质数；
- 选择序列中一个正整数 $A_i$（$1\le i\le N$），将 $A_i$ 变为 $\frac{A_i}{P}$，$P$ 为任意质数，要求 $A_i$ 是 $P$ 的倍数。
小 A 想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。
输入格式
第一行一个正整数 $N$，含义如题面所示。
第二行包含 $N$ 个正整数 $A_1,A_2,\ldots,A_N$，代表序列 $A$。
输出格式
输出一行，代表最少需要花费的金币数量。
输入输出样例 #1
输入 #1
1
2
5
10 6 35 105 42
输出 #1
1
8
说明/提示
对于 $60\%$ 的测试点，保证 $1\le N,A_i\le 100$。
对于所有测试点，保证 $1\le N,A_i\le 10^5$。
题目分析
本题的本质是考察质因数分解与中位数贪心。
1. 问题转化
题目中允许的两种操作：
- 将 $A_i$ 乘以一个质数 $P$（代价 $1$）。
- 将 $A_i$ 除以一个质数 $P$（代价 $1$）。
这实际上是在调整 $A_i$ 的质因数分解中各个质因子的指数。
设 $A_i = p_1^{e_{i,1}} \times p_2^{e_{i,2}} \times \dots$，最终目标是将所有数变为 $T = p_1^{k_1} \times p_2^{k_2} \times \dots$。 对于某一个特定的质数 $p$，将 $A_i$ 中的指数 $e_i$ 变为目标指数 $k$ 的代价就是 $|e_i - k|$。 总代价为所有书在所有质因数上的指数变化代价之和： \(Cost = \sum_{质数p} \sum_{i=1}^{N} |e_{i,p} - k_p|\)
由于各个质因数的指数调整是相互独立的，我们可以对每一个质数单独考虑。
2. 中位数贪心
对于某一个质数 $p$，我们在 $N$ 个数字中对应的指数分别为 $e_{1}, e_{2}, \dots, e_{N}$（注意：如果某个数 $A_i$ 不包含质因子 $p$，则其对应指数为 $0$）。 我们要找一个整数 $k$，使得 \(\sum_{i=1}^{N} |e_{i} - k|\) 最小。 这是一个经典的几何中位数性质的应用：在一维数轴上，到所有点距离之和最小的点是这些点的中位数。
3. 算法流程
- 预处理质数：使用线性筛（欧拉筛）预处理出 $1 \sim 10^5$ 范围内的素数。
- 分解质因数：对输入的 $N$ 个数进行质因数分解，统计每个质数在所有数中出现的指数。
- 使用
vector<int> factors[MAXN]来存储每个质数的非零指数列表。
- 使用
- 计算代价：
- 遍历所有出现过的质数。
- 对于质数 $p$，其具体的指数列表应包含所有的非零指数以及若干个 $0$（补齐 $N$ 个）。
- 将非零指数排序，结合补齐的 $0$，找到这 $N$ 个指数的中位数。
- 计算该质数下的总代价：所有指数与中位数的差的绝对值之和。
- 累加答案：将所有质数的代价累加即为最终结果。
4. 细节处理
隐式零的处理：在处理每个质数 $p$ 时，若其非零指数有 $m$ 个，则意味着有 $N-m$ 个数为 $0$。我们无需显式存储这些 $0$。
- 设排序后的非零指数列表为 $V$（下标 $0 \dots m-1$）。
全体 $N$ 个指数排序后的中位数下标为 $mid = \lfloor N/2 \rfloor$（以 0 为起始索引）。
- 判断逻辑：
- 若 $mid < N-m$，说明中位数落在前缀的 $0$ 序列中，即中位数 $k = 0$。
- 若 $mid \ge N-m$，说明中位数落在非零序列中，即中位数 $k = V[mid - (N-m)]$。
- 代价计算：
- 对于 $N-m$ 个 $0$，其代价之和为 $(N-m) \cdot |0 - k| = (N-m) \cdot k$。
- 对于 $m$ 个非零指数，遍历 $V$ 累加 $|V_i - k|$ 即可。
- 这种方法避免了为每个质数开辟长度为 $N$ 的数组，将空间复杂度优化至与所有数的质因数总数线性相关。
5. 时间复杂度
- 筛质数 $O(\max(A_i))$。
- 分解质因数 $O(N \sqrt{\max(A_i)})$ 或更优（取决于实现，题目中预处理了质数，分解较快）。
- 计算代价主要取决于排序，最坏情况下所有数的质因数个数总和相关，远小于 $O(N \log N)$ 级别。
- 总体可以在 1s 内通过。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
typedef long long ll;
const int MAXN = 100005;
int a[MAXN];
// primes_ary 用于线性筛标记合数
int primes_ary[MAXN];
std::vector<int> primes;
// 记录每个质数在各数字中的指数列表。
// key: 质数 p (作为数组下标)
std::vector<int> factors[MAXN];
int main() {
int N;
std::cin >> N;
for (int i = 1; i <= N; i++) {
std::cin >> a[i];
}
// 预处理 1 到 100005 之间的所有质数
primes_ary[1] = 1; // 1 不是质数
for (int i = 2; i < MAXN; i++) {
if (primes_ary[i] == 0) {
primes.push_back(i);
}
// 遍历已有的质数，标记合数
for (int j = 0; j < primes.size(); j++) {
// 如果超出范围则停止
if ((ll)primes[j] * i >= MAXN) {
break;
}
primes_ary[primes[j] * i] = 1;
// 欧拉筛的核心：如果 i 是 prime[j] 的倍数，说明 i
// 已经被更小的质因子筛过了
// 此时停止，保证每个合数只被其最小质因子筛一次，达到 O(N) 复杂度。
if (i % primes[j] == 0) {
break;
}
}
}
for (int i = 1; i <= N; i++) {
int tmp = a[i];
// 分解质因数
for (int p : primes) {
// 如果 p*p > tmp，说明剩下的 tmp 要么是 1，要么是一个大于
// sqrt(a[i]) 的质数。
// 这样可以提前退出循环，避免无效遍历，显著降低复杂度。
if (1LL * p * p > tmp) {
break;
}
if (tmp % p == 0) {
int exponent = 0;
while (tmp % p == 0) {
tmp /= p;
exponent++;
}
// 将质因数 p 的指数 exponent（即p出现的字数） 存入对应的 vector
// 中
factors[p].push_back(exponent);
}
}
// 处理最后剩下的那个较大的质因子
if (tmp > 1) {
factors[tmp].push_back(1);
}
}
ll ans = 0;
// 计算最小代价 ---
// 遍历每一个出现过的质因数
for (int p : primes) {
std::vector<int> exps = factors[p];
// 1. 对非零指数进行排序
std::sort(exps.begin(), exps.end());
// 2. 确定中位数
// 序列总长度应为 N（包含 exps 中的非零值和 (N - exps.size()) 个 0）
// 逻辑上的完整列表可以看作： [0, 0, ..., 0, exps[0], exps[1], ...]
int num_zeros = N - exps.size();
int mid_idx = N / 2; // 中位数在逻辑列表中的下标（0-indexed）
int median = 0;
if (mid_idx >= num_zeros) {
// 如果中位数下标落在了非零部分（即 exps 数组中）
// 对应的 exps 下标为 mid_idx - num_zeros
median = exps[mid_idx - num_zeros];
} else {
// 如果中位数下标落在 0 的区域
median = 0;
}
// 3. 计算由于该质因数产生的代价
// 代价 = sum(|x - median|)
// (1) 那些值为 0 的数贡献的代价： |0 - median| * num_zeros = median *
// num_zeros
ll cost = (ll)median * num_zeros;
// (2) 那些非零的数贡献的代价
for (int e : exps) {
cost += std::abs(e - median);
}
ans += cost;
}
std::cout << ans << '\n';
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
