题解 CF1292D 【Chaotic V.】

xht

2020-01-23 02:00:59

Solution

本题其实很暴力。 主要思路就是,先将点数减小到 $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; } ```