P14918 [GESP202512 五级] 相等序列
题目描述
小 A 有一个包含 N 个正整数的序列 A={A_1, A_2, ..., A_N}。小 A 每次可以花费 1 个金币执行以下任意一种操作：
- 选择序列中一个正整数 A_i（1≤i≤N），将 A_i 变为 A_i × P，P 为任意质数；
- 选择序列中一个正整数 A_i（1≤i≤N），将 A_i 变为 A_i / P，P 为任意质数，要求 A_i 是 P 的倍数。
小 A 想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。
输入格式
第一行一个正整数 N，含义如题面所示。
第二行包含 N 个正整数 A_1, A_2, ..., A_N，代表序列 A。
输出格式
输出一行，代表最少需要花费的金币数量。
输入输出样例 #1
输入 #1
5 10 6 35 105 42
输出 #1
8
说明/提示
对于 60% 的测试点，保证 1≤N, A_i≤100。
对于所有测试点，保证 1≤N, A_i≤10^5。
题解思路
一、核心分析
你需要解决的问题是通过最少的金币让序列中所有数相等，核心要点在于理解操作的本质：
- 每次操作是对某个数的质因数指数进行±1（乘质数等价于指数 +1，除质数等价于指数 -1），每次操作花费 1 金币。
- 因此问题可拆解为：对每个质数，调整所有数中该质数的指数到同一个值（最小化总花费），最终将所有质数的花费累加，即为答案。
关键性质
对于一个数组，要调整所有元素到同一个值且总绝对差最小，这个值是数组的中位数（中位数的核心性质：最小化绝对偏差和）。
二、解法步骤
整体分为三步：
- 质因数分解：将每个数分解为质因数的乘积，统计每个质数在不同数中的指数出现次数。
- 找中位数：对每个质数，统计其所有数的指数分布，找到该分布的中位数（最优调整目标）。
- 计算总花费：对每个质数，计算所有数的指数到中位数的绝对差之和，累加得到总金币数。
#include<bits/stdc++.h>
using namespace std;
// 全局变量定义
int n; // 序列中元素的个数
int a; // 临时存储输入的每个数
// m[i][j]：质数 i 的指数为 j 的数的个数（i 最大 1e5，j 最大约 17<20，足够覆盖）
int m[100005][25];
long long ans = 0; // 总花费（用 long long 避免 int 溢出）
{
( i = ; i * i <= x; i++) {
cnt = ;
(x % i == ) {
x /= i;
cnt++;
}
(cnt > ) {
m[i][cnt]++;
}
}
(x > ) {
m[x][]++;
}
;
}
{
cin >> n;
( i = ; i <= n; i++) {
cin >> a;
(a);
}
( prime = ; prime <= ; prime++) {
sum_non_zero = ;
( exp = ; exp < ; exp++) {
sum_non_zero += m[prime][exp];
}
m[prime][] = n - sum_non_zero;
median_exp = ;
cnt = ;
( exp = ; exp < ; exp++) {
cnt += m[prime][exp];
(cnt * >= n) {
median_exp = exp;
;
}
}
( exp = ; exp < ; exp++) {
ans += ( )m[prime][exp] * (exp - median_exp);
}
}
cout << ans << endl;
;
}
