题解：P14918 [GESP202512 五级] 相等序列

lcfollower · 2025-12-30 19:27:00 · 题解

被黄题打败了，QwQ，还是太菜了。

考虑分解质因数，这步应该都想得到，对于每个 a_i 都能被分解为 a_i = \prod\limits_{p_j\in \text{prime}}p_j^{r_j}。

现在对于乘/除一个质数，都相当于对于 r_i 这个指数增加 1 或减少 1。

然后我们也规定最后这个相同的数 x 被分解为 x = \prod\limits_{p_j\in \text{prime}}p_j^{R_j}。

单独地对于每个 p_j，我们都要找到一个 R_j 使得这些 r_j 经过增加或者减少 1 变成 R_j 的步数尽可能少。特别地，对于不能分解出 p_j 的 a_i，为了方便处理我们把它当作 r_j = 0。

首先把一个指数 r 变成 R 的最少步数为它们的绝对值，即 \lvert R - r\rvert。

然后问题转化为给定一个序列 \{b_i\}，让你求 \sum\limits_{i = 1}^n \lvert b_i - R\rvert 的最小值。

这个 R 取 \{b_i\} 的中位数最优，结论好证，用反证法，也可以搜，应该都知道？

然后就好做了，我们对于一个质数 p，对于每个 a_i 的非 0 的指数就加入 vector（最坏空间为 \mathcal O(nk)，k 为最大的整数满足 \prod\limits_{i = 1}^k p_i \le 10^5，p_i\in \text{prime} 且从小到大排序，不会超）。

但是如果之后统计答案：

• 暴力枚举每个质数然后分解质因数会 TLE。

• 暴力把 0 加入 vector 会 MLE。

• 暴力把 0 加入新开的数组会 TLE。

因此考虑如何求中位数。

我们假设有 len 个非 0 指数。

由于每个数都要加入（有的值为 0），因此最终加了 0 的大小总为 n，于是中位数下标为 pos = \lfloor \frac{n+1}{2}\rfloor，有 n - len 个 0 指数。

• 如果 n - len \ge pos，说明这个中位数 mid = 0。

• 否则 mid = b_{pos - (n - len)}，b 从小到大排序。

• 最后对答案的贡献即为 (n - len) \times mid + \sum\limits_{r_i \neq 0} \lvert mid - r_i\rvert。

然后就没了，时间复杂度和空间复杂度都不会超。

namespace lolcrying {

    inline void Euler(int n){
        isprime[1] = 1 ;
        up(i ,2 ,n) { // 筛素数。
            if(!isprime[i]) prime[++ cnt] = i ,isprime[i] = 0 ;
            for(int j = 1 ; j <= cnt && i * prime[j] <= n ; j ++){
                isprime[i * prime[j]] = 1;
                if(i % prime[j] == 0) break;
            }
        }
    } signed main(){

        n = read();
        up(i ,1 ,n) a[i] = read();

        Euler(1e5);

        up(i ,1 ,n) {
            for(int j = 2 ; j * j <= a[i] ; j ++) { // 分解质因数。
                if(isprime[j]) continue;
                int tot = 0 ;
                while(a[i] % j == 0) {
                    a[i] /= j ,++ tot;
                } vec[j].push_back(tot);
            }
            if(!isprime[a[i]]) vec[a[i]].push_back(1); // 别忘了。
        }

        int ans = 0 ;
        up(i ,1 ,cnt) {
/* 下述过程同上。*/
            int p = prime[i];
            int len = vec[p].size();
            if(!len) continue; // 没有肯定没贡献。

            up(j ,0 ,len - 1) b[j + 1] = vec[p][j];

            /*stable_*/sort(b + 1 ,b + 1 + len);

            int cut = ((n + 1) >> 1);
            int mid = (n - len >= cut ? 0 : b[cut - (n - len)]);

            up(j ,1 ,len) ans += abs(b[j] - mid);
            ans += mid * (n - len);

        } writeln(ans);

        return 0 ;
    }

}