题解 CF1292D 【Chaotic V.】
xht
2020-01-23 02:00:59
本题其实很暴力。
主要思路就是,先将点数减小到 $n = 5 \times 10^3$。
假设答案为 $1$,然后每次往最大的子树走,如果答案能够更优则更新答案,否则输出答案即可。
考虑细节上的问题,第一点是,由于点数太大,图是无法显式建出来的。
如何隐式建图呢?
首先可以将 $1! \sim n!$ 的所有质因数以及幂次数都求出来,具体来说就是求出 $1 \sim n$ 的然后做一个前缀和即可。
然后对于每个 $i$ 建立一个指针 $p_i$ 指向 $i!$ 的最大质因数,特别地如果 $c_i$(即 $i$ 出现的次数)为零则最大质因数默认为 $1$。
那么每次往一棵子树走的时候,动态维护这个指针即可。
接下来考虑时间复杂度。
由于一个点的可重质因子个数是 $\mathcal O(\log n)$ 级别的,因此最多走 $\mathcal O(n \log n)$ 条边。
每走一条边需要均摊 $\mathcal O(n)$ 的时间维护。
总时间复杂度 $\mathcal O(n^2 \log n)$。
```cpp
const int N = 5e3 + 1;
int n, c[N], f[N][N], p[N], s[N];
ll ans, now;
int main() {
rd(n);
for (int i = 1, x; i <= n; i++) rd(x), ++c[x];
for (int i = 2; i < N; i++) {
memcpy(f[i], f[i-1], sizeof(f[i]));
for (int j = 2, k = i; j <= k; j++)
while (k % j == 0) ++f[i][j], k /= j;
}
for (int i = 1; i < N; i++)
if (!c[i]) p[i] = 1;
else for (int j = 1; j <= i; j++)
if (f[i][j]) p[i] = j, now += 1ll * f[i][j] * c[i];
ans = now;
while (*max_element(p + 1, p + N) > 1) {
memset(s, 0, sizeof(s));
for (int i = 0; i < N; i++) s[p[i]] += c[i];
int o = max_element(s + 1, s + N) - s, w = s[o];
if (w * 2 <= n || o == 1) break;
ans = min(ans, now -= w * 2 - n);
for (int i = 0; i < N; i++) {
if (p[i] != o) p[i] = 1;
if (p[i] == 1) continue;
--f[i][p[i]];
while (p[i] > 1 && !f[i][p[i]]) --p[i];
}
}
print(ans);
return 0;
}
```