OneCoder Avatar
OneCodercoderli.com · 1025 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++ 五级真题解析,[2025年12月,第十二次认证]第二题-相等序列 luogu-p14918

📅 2026-01-07·✍️ OneCoder·计算中...·⏱️ 12 分钟

GESP C++ 2025年12月,五级真题第二题,考察数论与贪心算法思想,对考试来说有一定难度。题目难度⭐⭐⭐☆☆。洛谷难度等级普及/提高−。

P14918 [GESP202512 五级] 相等序列

题目要求

题目描述

小 A 有一个包含 个正整数的序列 。小 A 每次可以花费 个金币执行以下任意一种操作:

  • 选择序列中一个正整数 (),将 变为 , 为任意质数;
  • 选择序列中一个正整数 (),将 变为 , 为任意质数,要求 是 的倍数。

小 A 想请你帮他计算出令序列中所有整数都相同,最少需要花费多少金币。

输入格式

第一行一个正整数 ,含义如题面所示。

第二行包含 个正整数 ,代表序列 。

输出格式

输出一行,代表最少需要花费的金币数量。

输入输出样例 #1

输入 #1
PLAINTEXT2 行
5
10 6 35 105 42
输出 #1
PLAINTEXT1 行
8

说明/提示

对于 的测试点,保证 。

对于所有测试点,保证 。


题目分析

本题的本质是考察质因数分解与中位数贪心。

1. 问题转化

题目中允许的两种操作:

  1. 将 乘以一个质数 (代价 )。
  2. 将 除以一个质数 (代价 )。

这实际上是在调整 的质因数分解中各个质因子的指数。

设 ,最终目标是将所有数变为 。 对于某一个特定的质数 ,将 中的指数 变为目标指数 的代价就是 。 总代价为所有书在所有质因数上的指数变化代价之和:

由于各个质因数的指数调整是相互独立的,我们可以对每一个质数单独考虑。

2. 中位数贪心

对于某一个质数 ,我们在 个数字中对应的指数分别为 (注意:如果某个数 不包含质因子 ,则其对应指数为 )。 我们要找一个整数 ,使得 最小。 这是一个经典的几何中位数性质的应用:在一维数轴上,到所有点距离之和最小的点是这些点的中位数。

3. 算法流程

  1. 预处理质数:使用线性筛(欧拉筛)预处理出 范围内的素数。
  2. 分解质因数:对输入的 个数进行质因数分解,统计每个质数在所有数中出现的指数。
    • 使用 vector<int> factors[MAXN] 来存储每个质数的非零指数列表。
  3. 计算代价:
    • 遍历所有出现过的质数。
    • 对于质数 ,其具体的指数列表应包含所有的非零指数以及若干个 (补齐 个)。
    • 将非零指数排序,结合补齐的 ,找到这 个指数的中位数。
    • 计算该质数下的总代价:所有指数与中位数的差的绝对值之和。
  4. 累加答案:将所有质数的代价累加即为最终结果。

4. 细节处理

隐式零的处理:在处理每个质数 时,若其非零指数有 个,则意味着有 个数为 。我们无需显式存储这些 。

  • 设排序后的非零指数列表为 (下标 )。

  • 全体 个指数排序后的中位数下标为 (以 0 为起始索引)。

  • 判断逻辑:

    • 若 ,说明中位数落在前缀的 序列中,即中位数 。
    • 若 ,说明中位数落在非零序列中,即中位数 。
  • 代价计算:

    • 对于 个 ,其代价之和为 。
    • 对于 个非零指数,遍历 累加 即可。
  • 这种方法避免了为每个质数开辟长度为 的数组,将空间复杂度优化至与所有数的质因数总数线性相关。

5. 时间复杂度

  • 筛质数 。
  • 分解质因数 或更优(取决于实现,题目中预处理了质数,分解较快)。
  • 计算代价主要取决于排序,最坏情况下所有数的质因数个数总和相关,远小于 级别。
  • 总体可以在 1s 内通过。

示例代码

C++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;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!