A21990. 相等序列
填空题
困难
知识点
题目描述
相等序列
题目描述
小A有一个包含N个正整数的序列A={A1,A2,...,AN}。小A每次可以花费1个金币执行以下任意一种操作:
- 选择序列中一个正整数Ai(1≤i≤N)，将Ai变为Ai×P，P为任意质数;
- 选择序列中一个正整数Ai(1≤i≤N)，将Ai变为Ai/P，P为任意质数，要求Ai能整除P。
小A想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。
输入格式
第一行一个正整数N，含义如题面所示。
第二行包含N个正整数A1,A2,...,AN，代表序列A。
输出格式
输出⼀⾏，代表最少需要花费的⾦币数量。
样例
输入样例
5
10 6 35 105 42输出样例
8数据范围
对于60%的测试点，保证1≤N,Ai≤100。
对于所有测试点，保证1≤N,Ai≤105。
参考答案
#include <iostream>
using namespace std;
const int N = 100010;
int num[N][20];
int n, a[N];
void calc_prime_factor(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0){
int cnt=0;
while(x%i==0){
x/=i;
cnt++;
}
num[i][cnt]++;
}
}
if(x>1){
num[x][1]++;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
calc_prime_factor(a[i]);
}
long long ans=0;
for(int i=2;i<100001;i++){
int pos = 0;
for(int j=0;j<20;j++){
pos += num[i][j];
}
num[i][0]=n-pos;
int median_exponent=0;
pos = 0;
for(int j=0;j<20;j++){
pos += num[i][j];
if(pos*2>=n){
median_exponent=j;
break;
}
}
for(int j=0;j<20;j++){
ans+=num[i][j]*abs(j-median_exponent);
}
}
printf("%lld\n",ans);
}
上一题
下一题