GESP 题解库 / 5 级题解 / [GESP202512 五级] 相等序列 · 第 3 / 23 题
GESP202512 五级 · P14918 · 中等

相等序列

每次花 1 金币可给某个数乘或除以一个质数,求让所有数相等的最少金币。

📊
N, Aᵢ ≤ 10⁵
数据范围
🔢
int
数值类型
⚡
O(N log A)
时间复杂度
🎯
质因数分解 + 中位数
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 N 个正整数。每次可花 1 个金币执行以下操作之一:

求让序列中所有整数都相等所需的最少金币数。

💡
人话翻译:每次操作相当于给某个数的质因数分解中某个质数的指数加 1 或减 1。要让所有数相等,就要让每个质数的指数在所有数中变成同一个值——而"让一组数变成相同"的最优值是它们的中位数(绝对值之和最小)。关键是:不同质数之间完全独立,可以分别处理。

🔍 关键词提取

质因数分解指数向量中位数性质独立分解

已知条件

项目说明
输入第一行 N;第二行 N 个正整数
输出最少金币数
数据范围1 ≤ N ≤ 10⁵,1 ≤ Aᵢ ≤ 10⁵
操作代价每个指数 ±1 花 1 金币
目标所有数完全相等

需要解决的问题

02
思维导图
整理解题思路的全貌
🧮 按质数独立取中位数
🔬 分解
对每个 Aᵢ 质因数分解
得到"质数 → 指数"表
Aᵢ ≤ 10⁵
用线性筛求最小质因子
🧩 独立分解
每个质数互不影响
因为操作只改一个指数
所以可以分开算再相加
这是关键洞察
📐 取中位数
把该质数在各数的指数收集起来
排序取中位数 m
代价 = Σ|eᵢ − m|
中位数使绝对差之和最小
⚠️ 易错点
忘了大质因子(如 105 的 7)
以为是取平均数
用筛法时数组开小
代价求和用 long long
03
样例手算推导
样例的指数矩阵分析

🧮 样例:A = {10, 6, 35, 105, 42},答案 8

先做质因数分解,列出每个数的指数向量。

Aᵢ分解2 的指数3 的指数5 的指数7 的指数
102 × 51010
62 × 31100
355 × 70011
1053 × 5 × 70111
422 × 3 × 71101
1
质数 2:指数列 [1, 1, 0, 0, 1]

排序后 0、0、1、1、1,中位数 = 1

代价 = |1−1| + |1−1| + |0−1| + |0−1| + |1−1|

= 0 + 0 + 1 + 1 + 0 = 2

质数 2 的代价:2

2
质数 3:指数列 [0, 1, 0, 1, 1]

排序后 0、0、1、1、1,中位数 = 1

代价 = 1 + 0 + 1 + 0 + 0 = 2

质数 3 的代价:2

3
质数 5:指数列 [1, 0, 1, 1, 0]

排序后 0、0、1、1、1,中位数 = 1

代价 = 0 + 1 + 0 + 0 + 1 = 2

质数 5 的代价:2

4
质数 7:指数列 [0, 0, 1, 1, 1]

中位数 = 1

代价 = 1 + 1 + 0 + 0 + 0 = 2

质数 7 的代价:2

📊 汇总

质数各数的指数中位数最小代价
21, 1, 0, 0, 112
30, 1, 0, 1, 112
51, 0, 1, 1, 012
70, 0, 1, 1, 112
合计——8

最少 8 金币 ✓

🔑
为什么取中位数而不是平均数?数学结论:对于一组数,使 Σ|xᵢ − t| 最小的 t 就是中位数(而不是平均数,平均数对应的是平方和最小)。本题的代价正好是绝对差之和,所以取中位数。

🧮 为什么各质数可以独立处理

这是本题最关键的洞察,务必理解。

1
一次操作的影响范围

操作是"乘或除以一个质数 P"

这只会让 P 的指数变化 ±1

所有其他质数的指数完全不变

不同质数的指数互不干扰

2
因此可以拆开算

最终目标:所有数的指数向量相同

等价于:对每个质数 p,所有数的 p 指数都相同

总代价 = 各质数代价之和

每个质数单独求最小值

✅ 独立分解,答案相加

3
举个反例理解"独立"

假设 A = {4, 8}(即 2² 和 2³)

只需把 8 除以 2(花 1 金币)→ 都是 4

这里只有质数 2 需要调整

其他质数的指数都是 0,代价为 0

✅ 代价 1

⚠️
注意质数表要覆盖所有出现的质因子:比如 105 = 3 × 5 × 7,质数 7 也必须纳入统计。所以实现时应该动态收集所有出现过的质数(用哈希表记录"质数 → 指数列表"),而不是只处理某个固定范围内的小质数。
04
解法对比
按质数独立取中位数 vs 直接考虑数值

⚔️ 解法对比

🟢 质因数分解 + 中位数(推荐) 推荐

分解出每个质数的指数列表,各自取中位数算代价

  • 时间 O(N log A)
  • N, A ≤ 10⁵ 轻松通过
  • 思路清晰、可证明最优
  • 代码 40 行左右
💡
核心实现:用 unordered_map<int, vector<int>> 记录"质数 → 各数中该质数的指数",然后对每个 vector 排序取中位数、累加绝对差。注意指数为 0 的情况也要计入。

🟠 枚举"目标值"

枚举可能的目标数 t,计算把所有数变成 t 的代价

  • 候选 t 太多(可能上万个)
  • 每次计算代价 O(N log A)
  • 复杂度过高
  • 而且 t 的取值难以界定
⚠️
为什么不行:目标值可能是任何正整数,比如 {6, 10} 的最优目标是 30(乘 5 和乘 3,各花 1)或 2(除以 2 和 5,花 2)…目标值空间太大,无法有效枚举。而从"指数维度"看问题,每个质数的候选值就只有 0 ~ 最大指数那几种,取中位数一步到位。

📈 性能对比

方案复杂度可行性
指数维度 + 中位数O(N log A)✅ 可行
枚举目标数值不可控❌ 不可行
05
算法流程图
分解质因数 → 各质数取中位数
开始筛出最小质因子表 spf[](到 10⁵)对每个 Aᵢ 做质因数分解把"质数 p → 指数 e"记录到 map<p, vector> 中对每个质数:把该质数在各数中的指数收集成完整列表(补 0)对指数列表排序,取中位数 m累加 Σ|eᵢ − m| 到答案输出总代价结束还有数字 → 继续分解
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧮 相等序列最小代价计算器

输入一组正整数,程序会分解质因数、按质数取中位数并累加代价。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 100005;
int spf[MAXV];                          // 最小质因子(smallest prime factor)

int main() {
    // 线性筛:预处理每个数的最小质因子
    for (int i = 0; i < MAXV; i++) spf[i] = i;
    for (int i = 2; (long long)i * i < MAXV; i++) {
        if (spf[i] == i) {              // i 是质数
            for (int j = i * i; j < MAXV; j += i)
                if (spf[j] == j) spf[j] = i;
        }
    }

    int n;
    scanf("%d", &n);

    // 记录"质数 -> 各数中该质数的指数列表"
    unordered_map<int, vector<int>> exps;

    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        while (x > 1) {
            int p = spf[x];
            int e = 0;
            while (x % p == 0) { x /= p; e++; }
            exps[p].push_back(e);
        }
    }

    long long ans = 0;
    for (auto &kv : exps) {
        vector<int> v = kv.second;
        // 指数为 0 的数也要计入(它们没贡献到这个 vector 里)
        while ((int)v.size() < n) v.push_back(0);

        sort(v.begin(), v.end());
        int med = v[n / 2];                       // 中位数
        for (int e : v) ans += abs(e - med);       // 累加绝对差
    }

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么要把 v 补到长度为 n?因为某个质数并不是在所有数里都出现。比如质数 7 只在 35、105、42 里出现,在 10、6 里的指数是 0。这些 0 也必须参与"求中位数"——否则中位数会偏大,代价算错。所以要把缺失的位置补 0。

📖 关键几行怎么看

代码作用为什么这样写
spf[] 筛法预处理最小质因子让分解变成"每次跳到一个质因子",效率高
while (x % p == 0) { x /= p; e++; }统计指数同一质因子可能重复出现多次
while (v.size() < n) v.push_back(0);补零缺失的小数要按指数 0 计入
int med = v[n / 2];取中位数排序后取中间位置,绝对差之和最小
⚠️
三个坑:① 没有把缺失的位置补 0(中位数偏大,答案偏小);② 忘了大质因子(105 的 7 也要统计);③ 答案可能较大,累加用 long long。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5
10 6 35 105 42
8题面样例
1
7
0只有一个数,已经相等
2
4 8
18 除以 2 得到 4,花 1 金币
3
2 2 2
0本来就全部相等
2
6 10
26 = 2×3、10 = 2×5;质数 3 指数 [1,0] 代价 1,质数 5 指数 [0,1] 代价 1,共 2
2
1 1
0全为 1
✅
自查清单:① 每个质数的指数列表补齐到 n 了吗?② 大质因子统计了吗?③ 答案是 long long 吗?

🚨 易错点清单

⚠️
忘记补 0:某质数不在所有数中出现时,缺失位置的指数应视为 0 参与中位数计算。
⚠️
漏掉大质因子:105 = 3 × 5 × 7,质数 7 也要统计。
⚠️
用平均数代替中位数:最小化绝对差之和要用中位数。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N log A + A log log A)
空间复杂度
O(A + 质数数 × N)
N, A 最大
10⁵
运算量
约 10⁶

时间怎么算的?

空间都用在哪?

需要 spf 数组(10⁵)和"质数 → 指数列表"的哈希表。

✅ 整体约 10⁶ 量级,瞬间完成。关键是把问题从"数值"转换到"指数维度"。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 最小质因子筛(线性/埃氏变体)
int spf[MAXV];
for (int i = 0; i < MAXV; i++) spf[i] = i;
for (int i = 2; (long long)i * i < MAXV; i++)
    if (spf[i] == i)
        for (int j = i * i; j < MAXV; j += i)
            if (spf[j] == j) spf[j] = i;

// 用 spf 做质因数分解
while (x > 1) {
    int p = spf[x], e = 0;
    while (x % p == 0) { x /= p; e++; }
    // 处理 (p, e)
}

// 中位数性质:使 Σ|xᵢ - t| 最小的 t 是中位数
// 应用场景:
//   - 一维"仓库选址"(使运输距离和最小)
//   - 本题(使指数调整次数最少)
//   - 各类"最小化绝对偏差和"问题

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
质因数分解用 spf 快速分解数论、约数、gcd/lcm 类题目
指数维度视角把整数看作指数向量乘法/除法操作类问题
中位数最优最小化绝对差之和选址、对齐、调整代价类问题
🌟
思考题:如果操作改成"每次把 Aᵢ 加 1 或减 1"(花 1 金币),做法会一样吗?(提示:会一样——那时的最优目标还是所有数的中位数,代价也是绝对差之和。但注意本题是"乘除质数"操作,所以要在指数维度上取中位数,而不是在数值本身取中位数——这是一个容易混淆的关键区别。)