Cluster Computing System

We have $n$ vertices. For every pair $l<r$, there is an edge with weight

$$w(l,r)=\gcd(p_l,p_{l+1},\ldots,p_r).$$

So yes, this is a complete graph. Also yes, trying all $O(n^2)$ edges is how you get your program politely removed from the time limit.

The important thing is that an edge $(l,r)$ crosses all consecutive gaps

$$l, l+1, \ldots, r-1,$$

where gap $i$ means the cut between $[1..i]$ and $[i+1..n]$.

Reframing the MST

A spanning tree on ordered vertices must somehow connect across every one of the $n-1$ gaps. If there is no chosen edge crossing gap $i$, then vertices on the left of that gap cannot reach vertices on the right. So every gap must be covered by at least one chosen edge.

Now look at Kruskal's algorithm. Suppose we process edges by increasing weight. If an edge $(l,r)$ has at least one gap inside $[l,r-1]$ that has not been crossed by any previously chosen edge, then this edge connects two currently separate components, so Kruskal can use it. If all those gaps were already crossed, then the whole interval is already connected through cheaper/equal edges, so this edge is useless.

That gives a clean equivalent process:

• each edge $(l,r)$ covers the range of gaps $[l,r-1]$;
• process edges by increasing cost;
• whenever an edge covers uncovered gaps, pay its cost once for each newly covered gap.

Why once per gap? If edge $(l,r)$ is useful, Kruskal adds exactly one graph edge, not many. But this edge can merge several adjacent components at once? In a normal graph edge only reduces the component count by $1$, so how can that match multiple gaps?

Here is the subtle bit: when an interval first becomes cheap enough, we do not need the exact long edge for every gap. For every newly covered gap inside the interval, there exists some edge of the same or lower cost that can be used to connect across it during Kruskal's process. The gap-based greedy is effectively computing the MST by the cut property: each gap gets assigned the cheapest interval edge crossing it. These assigned costs can always be realized as a tree on the line after sorting by cost. No magic, just the linear-order structure doing work instead of making us suffer.

So the answer is:

$$\sum_{i=1}^{n-1} c_i,$$

where

$$c_i=\min_{l\le i<r} \gcd(p_l,\ldots,p_r).$$

Now the problem becomes: compute the minimum gcd value among all subarrays crossing each gap.

Generating useful intervals

For a fixed right endpoint $r$, consider all gcds of subarrays ending at $r$:

$$\gcd(p_l,\ldots,p_r) \quad \text{for } 1\le l\le r.$$

There are only $O(\log A)$ distinct values, because as you extend a subarray leftward, the gcd can only decrease by dropping to a divisor. Standard gcd compression handles this:

Maintain pairs $(g, L)$ meaning there are subarrays ending at current $r$ with gcd $g$, and the relevant left boundary range starts at $L$. When adding $p_r$, take every previous gcd and replace it by $\gcd(g,p_r)$, also add the length-$1$ subarray. Merge equal gcds.

But we need intervals crossing gaps. If a group says that for left endpoints in some range $[L..R]$, the gcd of $p_l..p_r$ is $g$, then every such interval $[l,r]$ covers gaps $l..r-1$. The union over $l\in[L..R]$ is just gaps $L..r-1$. So this whole group gives one candidate operation:

• weight $g$;
• cover gaps $L..r-1$.

Collect all such operations for all right endpoints.

The number of operations is $O(n\log A)$, which is fine.

Applying operations greedily

Sort operations by weight. We need to assign each gap the first, hence cheapest, operation that covers it.

Use a DSU-next array, the classic “skip already painted positions” trick:

• next[i] points to the first not-yet-covered gap at or after i;
• when gap i is covered, set next[i] = find(i+1);
• to cover range $[l,r]$, repeatedly jump to the next uncovered gap.

For every newly covered gap, add the operation's weight to the answer.

Each gap is covered once, so the range-covering part is almost linear after sorting.

Correctness proof

Let gap $i$ be the separation between vertices $i$ and $i+1$.

First, any connected graph must contain at least one selected edge crossing every gap. Otherwise, vertices $1..i$ and $i+1..n$ would be disconnected. Therefore, for each gap $i$, the MST must pay at least the minimum edge weight among all edges crossing that gap, call it $c_i$.

Second, consider processing all interval edges in nondecreasing order and assigning each gap when it is first covered. The first edge that covers gap $i$ has exactly cost $c_i$, because all edges are processed by weight. So the greedy range-covering algorithm computes $\sum c_i$.

Third, these gap choices are attainable as a spanning tree. Add edges in the same order as the greedy process. Whenever a gap is first covered by an interval edge crossing it, that edge connects the component on the left side of some still-uncovered gap to the component on the right side, so it is a valid Kruskal edge. After all $n-1$ gaps are covered, all consecutive separations are bridged, so the graph is connected. Exactly $n-1$ successful connections are counted, hence this forms a spanning tree with cost $\sum c_i$.

The lower bound and construction match, so the computed value is the MST cost.

Complexity

For each position, there are $O(\log A)$ distinct gcd states. We create $O(n\log A)$ operations, sort them, and cover each of the $n-1$ gaps once.

Total complexity:

$$O(n\log A\log(n\log A))$$

Memory is $O(n\log A)$. With $n=2\cdot 10^5$, this is totally chill.