每次花 1 金币可给某个数乘或除以一个质数,求让所有数相等的最少金币。
给定 N 个正整数。每次可花 1 个金币执行以下操作之一:
Aᵢ × P(P 为任意质数)Aᵢ / P(P 为任意质数,要求 Aᵢ 是 P 的倍数)求让序列中所有整数都相等所需的最少金币数。
质因数分解指数向量中位数性质独立分解
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N;第二行 N 个正整数 |
| 输出 | 最少金币数 |
| 数据范围 | 1 ≤ N ≤ 10⁵,1 ≤ Aᵢ ≤ 10⁵ |
| 操作代价 | 每个指数 ±1 花 1 金币 |
| 目标 | 所有数完全相等 |
先做质因数分解,列出每个数的指数向量。
| Aᵢ | 分解 | 2 的指数 | 3 的指数 | 5 的指数 | 7 的指数 |
|---|---|---|---|---|---|
| 10 | 2 × 5 | 1 | 0 | 1 | 0 |
| 6 | 2 × 3 | 1 | 1 | 0 | 0 |
| 35 | 5 × 7 | 0 | 0 | 1 | 1 |
| 105 | 3 × 5 × 7 | 0 | 1 | 1 | 1 |
| 42 | 2 × 3 × 7 | 1 | 1 | 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
排序后 0、0、1、1、1,中位数 = 1
代价 = 1 + 0 + 1 + 0 + 0 = 2
质数 3 的代价:2
排序后 0、0、1、1、1,中位数 = 1
代价 = 0 + 1 + 0 + 0 + 1 = 2
质数 5 的代价:2
中位数 = 1
代价 = 1 + 1 + 0 + 0 + 0 = 2
质数 7 的代价:2
| 质数 | 各数的指数 | 中位数 | 最小代价 |
|---|---|---|---|
| 2 | 1, 1, 0, 0, 1 | 1 | 2 |
| 3 | 0, 1, 0, 1, 1 | 1 | 2 |
| 5 | 1, 0, 1, 1, 0 | 1 | 2 |
| 7 | 0, 0, 1, 1, 1 | 1 | 2 |
| 合计 | — | — | 8 |
最少 8 金币 ✓
Σ|xᵢ − t| 最小的 t 就是中位数(而不是平均数,平均数对应的是平方和最小)。本题的代价正好是绝对差之和,所以取中位数。这是本题最关键的洞察,务必理解。
操作是"乘或除以一个质数 P"
这只会让 P 的指数变化 ±1
所有其他质数的指数完全不变
不同质数的指数互不干扰
最终目标:所有数的指数向量相同
等价于:对每个质数 p,所有数的 p 指数都相同
总代价 = 各质数代价之和
每个质数单独求最小值
✅ 独立分解,答案相加
假设 A = {4, 8}(即 2² 和 2³)
只需把 8 除以 2(花 1 金币)→ 都是 4
这里只有质数 2 需要调整
其他质数的指数都是 0,代价为 0
✅ 代价 1
分解出每个质数的指数列表,各自取中位数算代价
unordered_map<int, vector<int>> 记录"质数 → 各数中该质数的指数",然后对每个 vector 排序取中位数、累加绝对差。注意指数为 0 的情况也要计入。枚举可能的目标数 t,计算把所有数变成 t 的代价
| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 指数维度 + 中位数 | O(N log A) | ✅ 可行 |
| 枚举目标数值 | 不可控 | ❌ 不可行 |
输入一组正整数,程序会分解质因数、按质数取中位数并累加代价。
点按钮开始 →
#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]; | 取中位数 | 排序后取中间位置,绝对差之和最小 |
long long。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 | 8 | 题面样例 |
1 | 0 | 只有一个数,已经相等 |
2 | 1 | 8 除以 2 得到 4,花 1 金币 |
3 | 0 | 本来就全部相等 |
2 | 2 | 6 = 2×3、10 = 2×5;质数 3 指数 [1,0] 代价 1,质数 5 指数 [0,1] 代价 1,共 2 |
2 | 0 | 全为 1 |
需要 spf 数组(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 类题目 |
| 指数维度视角 | 把整数看作指数向量 | 乘法/除法操作类问题 |
| 中位数最优 | 最小化绝对差之和 | 选址、对齐、调整代价类问题 |