本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题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​×PP 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【算法标签】#普及# #质数#【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;intn,a[N][20],p[10005],cur,isprime[100005],ans;// n: 数字个数, a: 存储质因数统计, p: 质数数组, cur: 质数个数, isprime: 判断质数并存储索引, ans: 答案intmain(){cinn;// 输入数字个数// 埃拉托色尼筛法预处理质数for(inti2;i100000;i){if(!isprime[i])// 如果i是质数{p[cur]i;// 将质数i存入数组pisprime[i]cur;// 记录质数i在数组p中的索引for(intjii;j100000;ji)// 标记i的所有倍数isprime[j]1;// 标记为非质数}}// 处理输入的n个数字for(inti1;in;i){intx;cinx;// 输入一个数字// 分解质因数for(intj1;p[j]*p[j]x;j)// 只需检查到sqrt(x){if(x%p[j]0)// 如果p[j]是x的质因数{intcnt0;// 记录当前质因数的指数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(inti1;icur;i)// 遍历所有质数for(intj1;a[i][j];j)// 遍历第i个质数的所有指数{if(a[i][j]n/2)// 如果该质因子指数出现的次数超过一半ansn-a[i][j];// 添加需要改变的个数elseansa[i][j];// 添加该指数出现的次数}coutansendl;// 输出结果return0;}【运行结果】5 10 6 35 105 42 8