题解：P15082 [ICPC 2024 Chengdu R] Magical Set
Leoliu9
·
·
题解
~TLE on #41 耗了我一整天啊......~
分析题目
像这种一堆元素往几个最终状态挤的，肯定是网络流了。
理想状态肯定是一个质因子一个质因子地除，但是能完成吗？
小定理：只要满足每个 a_i 的最终状态不重复，就一定能按照上述最优方法操作。
证明：想象一下，如果 a_i 在操作的时候，下一个状态（假设是 v）被 a_j 挡住了。此时不用管这个障碍，直接从上面越过去。这样的操作等价于让 a_i 留在 v，原本在 v 的 a_j 继续往后移。
为了方便，我们开一个 p 数组记录所有 a_i 的因数。
后续的每个点的编号，以及每个以值为下标的数组，都是离散化后的。
First Thought
第一想法是这样建图的（以样例为例）：
从 S 向每个 a_i 连边，每个 p_i 向 T 连边，容量为 1，费用为 0；每个数向它的所有因数连边，容量为 inf，费用为 1。跑最大费用最大流。
这样很好的模拟了题目的流程，但是这个图也太大了吧。p 数组的大小在特殊构造是可以达到 2\times 10^5 的。
Second Thought
优化建图，注意到 S 都连 a_i，T 都连 p_i 那么就是一个二分图。
这样边数就少了很多。
但是由于此时不是一步一步跳的，设 i 的质因子个数为 cnt_i（质因子个数不是种类数，比如 12 = 2^2\times 3 有三个质因子，而不是两种质因子），因此每条边的的费用为 cnt_{左部点}-cnt_{右部点}，黑边费用为 0。
点数仍然很多，使用 KM 算法或者 SPFA 每次推流是无法通过的。
Third Thought
发现贪心选，最终状态肯定是 cnt 越小越好，既然只要最终状态不重复就合法，那么对于每个 a_i，它只可能选 cnt 最小的 n 个因数，边数就压缩到 n^2 了，spfa 可过，告别 TLE on #41。
-
> **$p$ 数组**：
>
> 对于每个 $a_i$，暴力 $\mathcal{O}(n\sqrt{a_i})$ 枚举，求因数集合，然后排序加 unique，即得。这个数组后续也可以用来离散化。
> ```cpp
> for (int i = 1; i <= n; ++i) {
> cin >> a[i];
> for (int j = 1; j*j <= a[i]; ++j) {
> if (a[i]%j) continue;
> p[++t] = j;
> if (j*j == a[i]) continue;
> p[++t] = a[i]/j;
> }
> }
> sort(p+1, p+t+1);
> t = unique(p+1, p+t+1)-p-1;
>```
> **$cnt$ 数量**：
>
> 这个有点恶心。
>
> - 先讲一种对于单个数 $x$ 的求法：预处理 $\sqrt{x}$ 以内的质数，然后用 $x$ 逐一试除每个质数，统计 $cnt$，注意到最多只会有一个 $\sqrt{x}$ 以上的质因子，特判如果最后 $x>1$ 就再加一就行了。
> - 如果对每个 $p_i$ 都按上法处理，那~也许~就 TLE 了。所以先对每个 $a_i$ 处理 $cnt$，然后 dfs 它的每个因数：不妨设 $a_i = \sum p_{i}^{\alpha_i}$，那么每个因数形如 $fac=\sum p_{i}^{e_i}$，$e_i \leq \alpha_i$，直接枚举，那么 $cnt_{fac}=\sum e_i$，同时还可以处理 $a_i$ 的因数。
> ```cpp
>void getfac(int i, int cur, int tim, int val) {
> if (cur == pfac[i].size()) {
> int k = lower_bound(p+1, p+t+1, val)-p; //cnt都是存在离散化后的数组里的，下同
> cnt[k] = tim;
> fac[i].push_back(val);
> return ;
> }
> for (int j = 0; j <= pfac[i][cur].second; ++j) >{
> getfac(i, cur+1, tim, val);
> val *= pfac[i][cur].first, tim++;
> }
>}
> ```
> ```cpp
>for (int i = 1; i <= n; ++i) {
> int x = a[i];
> int k = lower_bound(p+1, p+t+1, a[i])-p;
> for (int j : prim) {
> if (j > x) break; //这个剪枝不能少啊
> int tim = 0;
> while (x%j == 0) {
> tim++;
> x /= j;
> }
> if (!tim) continue;
> pfac[i].push_back({j, tim});
> cnt[k] += tim;
> }
> if (x > 1) {
> pfac[i].push_back({x, 1});
> cnt[k]++;
> }
> getfac(i, 0, 0, 1);
> }
>```
AC code
-
### 写在前面
写代码不容易啊，调 TLE 更是累，这题是随机跳题跳出来的，从昨天下午调到今天早上，其实重要的在于过程中学到的技巧和心态，而不是看完正解代码写完的小个 AC，真正有成就感的结果是过程堆出来的。
### 你们想看的
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300005, P = 5e5+5, E = 2e6+5, inf = 0x3f3f3f3f3f3f3f3f;
int n, a[N], p[P], t, S, T, f[E], c[E], tot = -1, dis[P], mnf[P], inq[P], pree[P], prep[P], ans, cnt[P];
vector<int> prim, fac[N];
vector<pair<int, int>> pfac[N];
struct Edge {int v, id;};
vector<Edge> g[P];
bool cmp(int a, int b) {
int i = lower_bound(p+1, p+t+1, a)-p;
int j = lower_bound(p+1, p+t+1, b)-p;
return cnt[i] < cnt[j];
}
void addEdge(int u, int v, int flow, int cost) {
g[u].push_back({v, ++tot});
f[tot] = flow, c[tot] = cost;
g[v].push_back({u, ++tot});
f[tot] = 0, c[tot] = -cost;
}
bool np[40005];
void getprime() {
for (int i = 2; i <= 40000; ++i) {
if (!np[i]) prim.push_back(i);
for (int j : prim) {
if (j*i > 40000) break;
np[j*i] = 1;
if (i%j == 0) break;
}
}
}
void getfac(int i, int cur, int tim, int val) {
if (cur == pfac[i].size()) {
int k = lower_bound(p+1, p+t+1, val)-p;
cnt[k] = tim;
fac[i].push_back(val);
return ;
}
for (int j = 0; j <= pfac[i][cur].second; ++j) {
getfac(i, cur+1, tim, val);
val *= pfac[i][cur].first, tim++;
}
}
bool spfa() {
for (int i = S; i <= T; ++i) {
dis[i] = mnf[i] = inf;
prep[i] = pree[i] = inq[i] = 0;
}
queue<int> q;
dis[S] = 0, q.push(S);
inq[S] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = 0;
for (auto [v, id] : g[u]) {
if (f[id] && dis[v] > dis[u]+c[id]) {
dis[v] = dis[u]+c[id];
mnf[v] = min(mnf[u], f[id]);
prep[v] = u, pree[v] = id;
if (!inq[v]) {
q.push(v);
inq[v] = 1;
}
}
}
}
return dis[T] != inf;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
for (int j = 1; j*j <= a[i]; ++j) {
if (a[i]%j) continue;
p[++t] = j;
if (j*j == a[i]) continue;
p[++t] = a[i]/j;
}
}
sort(p+1, p+t+1);
t = unique(p+1, p+t+1)-p-1;
getprime();
for (int i = 1; i <= n; ++i) {
int x = a[i];
int k = lower_bound(p+1, p+t+1, a[i])-p;
for (int j : prim) {
if (j > x) break;
int tim = 0;
while (x%j == 0) {
tim++;
x /= j;
}
if (!tim) continue;
pfac[i].push_back({j, tim});
cnt[k] += tim;
}
if (x > 1) {
pfac[i].push_back({x, 1});
cnt[k]++;
}
getfac(i, 0, 0, 1);
}
S = 0, T = n+t+1;
for (int i = 1; i <= n; ++i)
addEdge(S, i, 1, 0);
for (int i = n+1; i <= n+t; ++i)
addEdge(i, T, 1, 0);
for (int i = 1; i <= n; ++i) {
sort(fac[i].begin(), fac[i].end(), cmp);
for (int j = 0; j < min((int)fac[i].size(), n); ++j) {
int I = lower_bound(p+1, p+t+1, a[i])-p;
int J = lower_bound(p+1, p+t+1, fac[i][j])-p;
addEdge(i, n+J, inf, -(cnt[I]-cnt[J]));
}
}
while (spfa()) {
ans += -dis[T]*mnf[T];
for (int cur = T; cur != S; cur = prep[cur]) {
f[pree[cur]] -= mnf[T];
f[pree[cur]^1] += mnf[T];
}
}
cout << ans;
return 0;
}
```