题解：P12579 [UOI 2021] 哥萨克与 GCD

ty_mxzhn · 2026-01-06 19:59:04 · 题解

一只眼睛题。但是还是写的详细一点。

首先考虑怎么知道所有 b_i。我们作 b 的前缀和 s_i。相当于知道 s_1,s_2,...,s_n 就可以还原了。

则问 [l,r] 可以知道 s_r-s_{l-1}。发现相当于知道 s_r 就可以知道 s_{l-1}，反之亦然。

连一条双向边 (r,l-1)，显然我们是知道 s_0 的，问题转化为 0 可以到所有点，也就是图连通，最小的话就是图的最小生成树。

问题变成最小生成树，在 (l,r) 之间连边代价是 \gcd(a_{l+1},...,a_{r})。

Kruskal 和 B 开头算法都不是很好用，考虑 Prim。

从 0 开始，第一步显然到 n，接下来没被到达的点是 [1,n-1]=[l,r]，每一步要么连 (l,n) 要么连 (0,r)。并且缩小区间。

发现这个还是不太好做。但是发现有用的边只有 (0,n),(0,i),(i,n)。发现实际上总代价是 \gcd[1,n]+\sum_{i=1}^{n-1}\min(\gcd[1,i],\gcd[i+1,n])。证明不难。

显然 \gcd[1,i]\le \gcd[i+1,n] 的是一个后缀。可以二分。

求前缀 \gcd 的前缀和，可以发现变化最多 \log V 次，可以暴力查找。

具体的，暴力递归，如果发现一个区间 [l,r] 满足 \gcd[1,l-1]=\gcd[1,r] 就直接计算。

时间复杂度 O(n\log^3 n)，跑不满。