匿名用户·2026/5/16markdown1# 相等序列 题解 2 3## 题目分析 4 5我们有一个长度为 $N$ 的正整数序列。每次操作可以选择一个数，**乘上任意质数**，或**除以任意质数**（要求该数是这个质数的倍数）。每次操作花费 $1$ 金币，目标是通过若干次操作使所有数相等，求最小花费。 6 7操作的本质是改变一个数的质因数分解中某个质数的**指数**： 8 9- 乘一个质数 $p$ → 该质数的指数 $+1$ 10- 除以一个质数 $p$ → 该质数的指数 $-1$ 11 12因此，最终使所有数相等，等价于让所有数的**每一个质因数的指数都对应相等**。 13 14由于乘除操作每次只影响一个质数，不同质数之间的操作是**相互独立**的。因此，我们可以**按质数分开考虑**：对于每一个质数 $p$，我们希望将所有数在 $p$ 上的指数调整成同一个值，并求出最小调整次数，最后将所有质数的答案相加即可。 15 16## 解题思路 17 18设质数 $p$ 在第 $i$ 个数中的指数为 $e_i$（如果 $p$ 不整除该数，则 $e_i = 0$）。我们需要选择一个目标指数 $t$（$t \ge 0$），使得 19$$ 20\sum_{i=1}^{N} |e_i - t| 21$$ 22最小。这是一个经典问题：**使曼哈顿距离和最小的点是数据的中位数**。 23 24也就是说，将 $e_1, e_2, \dots, e_N$ 排序后，**任何一个在中位数位置的整数都是最优的 $t$**。若 $N$ 为奇数，中位数唯一；若 $N$ 为偶数，则中间两个数之间的任意整数均可，一般取较小的那个即可。 25 26因此，对每一个出现过的质数 $p$（包括可能指数为 $0$ 的数也要考虑），只需： 271. 统计所有 $N$ 个数在 $p$ 上的指数分布； 282. 找到这些指数的中位数； 293. 计算每个指数到中位数的距离之和。 30 31最终将所有质数的距离之和累加，就是答案。 32 33## 算法说明 34 35由于 $A_i \le 10^5$，质因数最大不超过 $10<sup>5$，且每个数的质因数指数不会太大（$2</sup>{17} = 131072 > 10^5$，所以指数不超过 $17$）。我们可以用一个数组 `num[p][e]` 记录质数 $p$ 的指数为 $e$ 的数有多少个。 36 37具体步骤： 38 391. **质因数分解** 40 对每个 $A_i$，用试除法找出所有质因数及其指数，维护 `num[p][e]`。注意指数为 $0$ 的情况不需要显式存，最后用总数 $N$ 减去非零指数的总数即可得到指数 $0$ 的个数。 41 422. **按质数统计与求中位数** 43 遍历所有可能的质数 $p$（$2 \le p \le 10^5$）： 44 - 先补齐指数为 $0$ 的个数：`num[p][0] = N - Σ_{e>0} num[p][e]`。 45 - 从小到大累加 `num[p][e]`，当累计个数达到 $\lceil N/2 \rceil$ 时，当前的指数 $e$ 即为**中位数**。 46 - 计算该质数的贡献：$\sum_{e} \text{num}[p][e] \times |e - \text{median}|$，累加进答案。 47 483. **输出总代价**。 49 50## 时间复杂度分析 51 52- 质因数分解部分：对每个数试除到 $\sqrt{A_i}$，最坏 $O(N \sqrt{\max A}) \approx 10^5 \times 316 \approx 3 \times 10^7$，可以接受。 53- 统计与求和中位数部分：外层循环 $10^5$，内层循环指数维度约 $20$，总计约 $2 \times 10^6$。 54- 整体时间复杂度 $O(N \sqrt{\max A} + \max A \cdot \log \max A)$，在 $1$ 秒时限内足够。 55 56## 参考代码解释 57 58```cpp 59#include <iostream> 60using namespace std; 61const int N = 100010; 62int num[N][20]; // num[p][e] 表示质数p的指数为e的个数 63int n, a[N]; 64 65// 分解质因数，统计指数分布 66void calc_prime_factor(int x){ 67 for(int i = 2; i * i <= x; i++){ 68 if(x % i == 0){ 69 int cnt = 0; 70 while(x % i == 0){ 71 x /= i; 72 cnt++; 73 } 74 num[i][cnt]++; // 质数i，指数cnt的个数+1 75 } 76 } 77 if(x > 1){ 78 num[x][1]++; // 剩余的大于sqrt(x)的质数，指数为1 79 } 80} 81 82int main(){ 83 scanf("%d", &n); 84 for(int i = 1; i <= n; i++){ 85 scanf("%d", &a[i]); 86 calc_prime_factor(a[i]); 87 } 88 89 long long ans = 0; 90 for(int i = 2; i < 100001; i++){ // 枚举所有可能的质数 91 int pos = 0; 92 for(int j = 0; j < 20; j++){ 93 pos += num[i][j]; // 统计非零指数个数 94 } 95 num[i][0] = n - pos; // 补齐指数为0的个数 96 97 int median_exponent = 0; 98 pos = 0; 99 for(int j = 0; j < 20; j++){ // 寻找中位数指数 100 pos += num[i][j]; 101 if(pos * 2 >= n){ // 达到一半 102 median_exponent = j; 103 break; 104 } 105 } 106 107 for(int j = 0; j < 20; j++){ // 累加该质数的代价 108 ans += num[i][j] * abs(j - median_exponent); 109 } 110 } 111 printf("%lld\n", ans); 112}
num 数组第二维大小为 20，足以容纳 105 以内所有可能的质因数指数。i 从 2 开始，虽然 i 可能为合数，但由于 while(x % i == 0) 会将该质数的所有幂次除尽，后续的合数必然不会整除 x，因此能正确统计所有质因数。n 为偶数，取较小的中间数即可，不影响最小距离和）。long long，因为最坏情况下总代价可能超过 231−1。本题的关键是将“乘除质数”的操作转化为“调整质因数指数”，并利用不同质数之间独立的性质，将问题拆解为若干个一维曼哈顿距离最小化问题，最后用中位数求解。代码实现时要注意补齐指数为 0 的情况，并合理估计指数上限以节省空间。