G5020 [GESP202512 五级] 相等序列 题解

知识点：质因数分解、中位数、贪心。

解题思路

分解各数的质因数，对每个质数收集所有指数，未出现的数补指数0。将这一维指数统一到中位数，累加与中位数的绝对差。

为什么正确

一次乘除某质数只改变对应指数1，所有质数维度独立；绝对距离和在中位数处最小。

易错点

未记录的指数必须视为0，不能只在出现该质数的数中取中位数。

复杂度

筛界M时预处理O(M log log M)，其余O(n log M+Σ k_p log k_p)，空间O(M+n log M)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    const int M=100000;
    vector<int>spf(M+1);
    for(int i=2;i<=M;i++)if(!spf[i])for(int j=i;j<=M;j+=i)if(!spf[j])spf[j]=i;
    map<int,vector<int>>exps;
    for(int i=0;i<n;i++) {
        int x;
        cin>>x;
        while(x>1) {
            int p=spf[x],c=0;
            while(x%p==0) {
                x/=p;
                c++;
            }
            exps[p].push_back(c);
        }
    }
    long long ans=0;
    for(auto &[p,v]:exps) {
        sort(v.begin(),v.end());
        int zeros=n-v.size(),median=(n/2<zeros)?0:v[n/2-zeros];
        ans+=(long long)zeros*median;
        for(int x:v)ans+=abs(x-median);
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。