相等序列题解

思路：贪心+质因数分解，看代码吧
—————————————————————————————————————————

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,a[MAXN],p[MAXN][20],ans;
void f(int x){
    if(x==1)return;
    int t[MAXN]={0};
    for(int i=2;i*i<=x;i++){
        while(x%i==0){//分解质因子
            p[i][++t[i]]++;//p[i][j]存储的是第j个输入的数字a[j]中,质因子i出现的次数(指数)
            x/=i;
        }
        if(x==1)break;
    }
    if(x>1)p[x][++t[x]]++;//若除尽后x>1,说明剩下的x本身就是一个大于sqrt(原来x)的质因子
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f(a[i]);
    }
    for(int i=2;i<=1e5;i++){
        for(int j=1;j<20;j++){
            if(!p[i][j])break;
            ans+=min(p[i][j],n-p[i][j]);//少数凑合多数，p[i][j]存储要补上多少个质因子，几个质因子就是花费多少金币，n-p[i][j]求减少多少个质因子，同前面一样质因子数量就是花费多少金币,取最小值就是最小花费
        }
    }
    cout<<ans;
    return 0;
}