C++ 算法考级专栏
🎨 视觉封面【GESP】C++ 五级真题解析,[2025年12月,第十二次认证]第二题-相等序列 luogu-p14918
GESP C++ 2025年12月,五级真题第二题,考察数论与贪心算法思想,对考试来说有一定难度。题目难度⭐⭐⭐☆☆。洛谷难度等级普及/提高−。
P14918 [GESP202512 五级] 相等序列
题目要求
题目描述
小 A 有一个包含 个正整数的序列 。小 A 每次可以花费 个金币执行以下任意一种操作:
- 选择序列中一个正整数 (),将 变为 , 为任意质数;
- 选择序列中一个正整数 (),将 变为 , 为任意质数,要求 是 的倍数。
小 A 想请你帮他计算出令序列中所有整数都相同,最少需要花费多少金币。
输入格式
第一行一个正整数 ,含义如题面所示。
第二行包含 个正整数 ,代表序列 。
输出格式
输出一行,代表最少需要花费的金币数量。
输入输出样例 #1
输入 #1
5
10 6 35 105 42输出 #1
8说明/提示
对于 的测试点,保证 。
对于所有测试点,保证 。
题目分析
本题的本质是考察质因数分解与中位数贪心。
1. 问题转化
题目中允许的两种操作:
- 将 乘以一个质数 (代价 )。
- 将 除以一个质数 (代价 )。
这实际上是在调整 的质因数分解中各个质因子的指数。
设 ,最终目标是将所有数变为 。 对于某一个特定的质数 ,将 中的指数 变为目标指数 的代价就是 。 总代价为所有书在所有质因数上的指数变化代价之和:
由于各个质因数的指数调整是相互独立的,我们可以对每一个质数单独考虑。
2. 中位数贪心
对于某一个质数 ,我们在 个数字中对应的指数分别为 (注意:如果某个数 不包含质因子 ,则其对应指数为 )。 我们要找一个整数 ,使得 最小。 这是一个经典的几何中位数性质的应用:在一维数轴上,到所有点距离之和最小的点是这些点的中位数。
3. 算法流程
- 预处理质数:使用线性筛(欧拉筛)预处理出 范围内的素数。
- 分解质因数:对输入的 个数进行质因数分解,统计每个质数在所有数中出现的指数。
- 使用
vector<int> factors[MAXN]来存储每个质数的非零指数列表。
- 使用
- 计算代价:
- 遍历所有出现过的质数。
- 对于质数 ,其具体的指数列表应包含所有的非零指数以及若干个 (补齐 个)。
- 将非零指数排序,结合补齐的 ,找到这 个指数的中位数。
- 计算该质数下的总代价:所有指数与中位数的差的绝对值之和。
- 累加答案:将所有质数的代价累加即为最终结果。
4. 细节处理
隐式零的处理:在处理每个质数 时,若其非零指数有 个,则意味着有 个数为 。我们无需显式存储这些 。
-
设排序后的非零指数列表为 (下标 )。
-
全体 个指数排序后的中位数下标为 (以 0 为起始索引)。
-
判断逻辑:
- 若 ,说明中位数落在前缀的 序列中,即中位数 。
- 若 ,说明中位数落在非零序列中,即中位数 。
-
代价计算:
- 对于 个 ,其代价之和为 。
- 对于 个非零指数,遍历 累加 即可。
-
这种方法避免了为每个质数开辟长度为 的数组,将空间复杂度优化至与所有数的质因数总数线性相关。
5. 时间复杂度
- 筛质数 。
- 分解质因数 或更优(取决于实现,题目中预处理了质数,分解较快)。
- 计算代价主要取决于排序,最坏情况下所有数的质因数个数总和相关,远小于 级别。
- 总体可以在 1s 内通过。
示例代码
#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:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP】C++五级真题(数论, 贪心思想考点) luogu-B4070 [GESP202412 五级] 奇妙数字
GESP C++ 2024年12月五级真题,数论和贪心思想考点,又见质因数分解,5级似乎很喜欢考这个题型,题目难度⭐⭐⭐☆☆,五级正常难度。洛谷难度等级普及/提高−
【GESP】C++五级真题(数论、贪心考点) luogu-P14073 [GESP202509 五级] 数字选取
GESP C++ 2025年9月五级真题,数论、贪心考点,题目难度⭐⭐★☆☆,五级来说难度相对简单。洛谷难度等级普及−
【GESP】C++五级练习(初等数论考点) luogu-B3941 [GESP样题 五级] 小杨的锻炼
GESP C++ 五级初等数论考点练习,难度⭐⭐★☆☆。洛谷难度等级普及−
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

