GESP认证C++编程真题解析 | P14918 [GESP202512 五级] 相等序列

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[P14918 GESP202512 五级] 相等序列 - 洛谷

【题目描述】

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

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

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

【输入】

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

第二行包含N NN个正整数A 1 , A 2 , … , A N A_1,A_2,\ldots,A_NA1​,A2​,…,AN​，代表序列A AA。

【输出】

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

【输入样例】

5 10 6 35 105 42

【输出样例】

8

【算法标签】

《洛谷 P14918 相等序列》 #贪心# #数论# #素数判断,质数,筛法# #GESP# #2025#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;intn,a[N][20],p[10005],cur,isprime[100005],ans;// n: 数字个数, a: 存储质因数统计, p: 质数数组, cur: 质数个数, isprime: 判断质数并存储索引, ans: 答案intmain(){cin>>n;// 输入数字个数// 埃拉托色尼筛法预处理质数for(inti=2;i<=100000;i++){if(!isprime[i])// 如果i是质数{p[++cur]=i;// 将质数i存入数组pisprime[i]=cur;// 记录质数i在数组p中的索引for(intj=i+i;j<=100000;j+=i)// 标记i的所有倍数isprime[j]=1;// 标记为非质数}}// 处理输入的n个数字for(inti=1;i<=n;i++){intx;cin>>x;// 输入一个数字// 分解质因数for(intj=1;p[j]*p[j]<=x;j++)// 只需检查到sqrt(x){if(x%p[j]==0)// 如果p[j]是x的质因数{intcnt=0;// 记录当前质因数的指数while(x%p[j]==0)// 计算质因数p[j]的指数{cnt++;a[j][cnt]++;// 统计第j个质数的cnt次方在n个数字中出现的次数x/=p[j];// 除掉这个质因数}}}if(x)// 如果x还有剩余的质因数（x本身是质数且大于sqrt(原x)）a[isprime[x]][1]++;// 统计这个质数的一次方}// 计算结果for(inti=1;i<=cur;i++)// 遍历所有质数for(intj=1;a[i][j];j++)// 遍历第i个质数的所有指数{if(a[i][j]>n/2)// 如果该质因子指数出现的次数超过一半ans+=n-a[i][j];// 添加需要改变的个数elseans+=a[i][j];// 添加该指数出现的次数}cout<<ans<<endl;// 输出结果return0;}

【运行结果】

5 10 6 35 105 42 8