CCF-GESP计算机学会等级考试2025年12月五级C++T2 相等序列-平芜编程栈

P14918 [GESP202512 五级] 相等序列

题目描述

小 A 有一个包含NNN个正整数的序列A={A1,A2,…,AN}A=\{A_1,A_2,\ldots,A_N\}A={A1,A2,…,AN}。小 A 每次可以花费111个金币执行以下任意一种操作：

选择序列中一个正整数AiA_iAi（1≤i≤N1\le i\le N1≤i≤N），将AiA_iAi变为Ai×PA_i\times PAi×P，PPP为任意质数；
选择序列中一个正整数AiA_iAi（1≤i≤N1\le i\le N1≤i≤N），将AiA_iAi变为AiP\frac{A_i}{P}PAi，PPP为任意质数，要求AiA_iAi是PPP的倍数。

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

输入格式

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

第二行包含NNN个正整数A1,A2,…,ANA_1,A_2,\ldots,A_NA1,A2,…,AN，代表序列AAA。

输出格式

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

输入输出样例 #1

输入 #1

5 10 6 35 105 42

输出 #1

说明/提示

对于60%60\%60%的测试点，保证1≤N,Ai≤1001\le N,A_i\le 1001≤N,Ai≤100。

对于所有测试点，保证1≤N,Ai≤1051\le N,A_i\le 10^51≤N,Ai≤105。

【题解】P14918 [GESP202512 五级] 相等序列

一、题目核心分析

你需要解决的问题是通过最少的金币让序列中所有数相等，核心要点在于理解操作的本质：

每次操作是对某个数的质因数指数进行±1（乘质数等价于指数+1，除质数等价于指数-1），每次操作花费1金币。
因此问题可拆解为：对每个质数，调整所有数中该质数的指数到同一个值（最小化总花费），最终将所有质数的花费累加，即为答案。

关键性质

对于一个数组，要调整所有元素到同一个值且总绝对差最小，这个值是数组的中位数（中位数的核心性质：最小化绝对偏差和）。

二、解法思路

整体分为三步：

质因数分解：将每个数分解为质因数的乘积，统计每个质数在不同数中的指数出现次数。
找中位数：对每个质数，统计其所有数的指数分布，找到该分布的中位数（最优调整目标）。
计算总花费：对每个质数，计算所有数的指数到中位数的绝对差之和，累加得到总金币数。

#include<bits/stdc++.h>usingnamespacestd;// 全局变量定义intn;// 序列中元素的个数inta;// 临时存储输入的每个数// m[i][j]：质数i的指数为j的数的个数（i最大1e5，j最大约17<20，足够覆盖）intm[100005][25];longlongans=0;// 总花费（用long long避免int溢出，因为最大可能花费1e5*20=2e6，也可不用但养成习惯）/** * @brief 质因数分解函数：分解单个数字x，统计每个质因数的指数 * @param x 要分解的正整数 */voidfactorize(intx){// 试除法分解质因数，遍历到sqrt(x)即可for(inti=2;i*i<=x;i++){intcnt=0;// 记录当前质数i在x中的指数// 不断除以i，直到无法整除，统计指数while(x%i==0){x/=i;cnt++;}// 如果该质数i在x中存在（指数>0），更新统计数组if(cnt>0){m[i][cnt]++;}}// 若最后剩余的x>1，说明x本身是质数（未被分解），指数为1if(x>1){m[x][1]++;}return;}intmain(){// 第一步：输入序列长度和序列元素cin>>n;for(inti=1;i<=n;i++){cin>>a;factorize(a);// 对每个数进行质因数分解，更新统计数组m}// 第二步：遍历所有可能的质数（1e5以内），计算每个质数的最小花费for(intprime=2;prime<=100000;prime++){// 步骤2.1：统计该质数指数为0的数的个数（即序列中不含该质数的数）intsum_non_zero=0;// 指数≥1的数的个数for(intexp=0;exp<20;exp++){sum_non_zero+=m[prime][exp];}m[prime][0]=n-sum_non_zero;// 指数为0的数 = 总数n - 指数≥1的数// 步骤2.2：找该质数指数分布的中位数（中位数最小化绝对差和）intmedian_exp=0;// 最优调整目标：指数的中位数intcnt=0;// 累加指数的计数，用于找中位数for(intexp=0;exp<20;exp++){cnt+=m[prime][exp];// 累加当前指数exp的数的个数// 当累加数≥n/2时，找到中位数（n为奇数时取中间，偶数时取任意中间均可）if(cnt*2>=n){median_exp=exp;break;}}// 步骤2.3：计算该质数的总花费并累加到答案for(intexp=0;exp<20;exp++){// 每个指数exp的数有m[prime][exp]个，每个数需要调整|exp - median_exp|次ans+=(longlong)m[prime][exp]*abs(exp-median_exp);// 强制转换为long long避免乘法溢出（m[prime][exp]最大1e5，abs最大20，乘积2e6，也可不用但规范）}}// 第三步：输出总最小花费cout<<ans<<endl;return0;}

三、代码逐部分解析

1. 变量与数组定义

m[i][j]是核心数组：第一维表示质数i，第二维表示指数j，值为“序列中包含质数i且指数为j的数的个数”。
ans用long long是因为N和A_i最大为1e5，总花费可能超过int范围。

2. 质因数分解函数

功能：对单个数字做质因数分解，更新m数组统计指数分布。
试除法：从2到√x遍历，找到所有质因数及其指数；若最后x>1，说明x本身是质数，统计其指数为1。

3. 主函数逻辑

关键步骤解释：

统计指数0的个数：初始时m[i][0]为0，需要计算“没有该质数的数”的数量（即指数为0）。
找中位数k：通过累加指数j的计数s，当s×2≥n时，j就是中位数（例如n=5时，s≥3即找到中位数）。
计算单个质数的花费：每个指数j的数有m[i][j]个，每个数需要调整|j-k|次，总花费为m[i][j]×|j-k|，累加到ans。

五、总结

核心关键点

问题转化：将“乘/除质数”的操作转化为“调整质因数指数”，把原问题拆解为多个独立的“中位数最小化绝对差”子问题。
中位数最优：对单个质数的指数分布，选择中位数作为调整目标，能保证该质数的总花费最小。
质因数分解：用试除法高效分解1e5以内的数，确保时间复杂度可接受。

时间复杂度

质因数分解：每个数分解的时间为O(Ai)O(\sqrt{A_i})O(Ai)，总时间O(NAi)O(N\sqrt{A_i})O(NAi)（Ai≤1e5A_i≤1e5Ai≤1e5，Ai≈300\sqrt{A_i}≈300Ai≈300，N≤1e5N≤1e5N≤1e5，总操作约3e7，可通过）。
遍历质数：1e5以内的质数遍历，内层循环最多20次，时间可忽略。