In this task, we needed to find the minimum spanning tree in a graph where two nodes ~a~ and ~b~ are connected with weight ~\min(P_a \mathbin\% P_b, P_b \mathbin\% P_a)~. This expression is equal to ~P_a \mathbin\% P_b~ for ~P_a > P_b~ and vice-versa.

If two nodes exist with equal values, we can connect them with zero cost and observe them as a single node. Furthermore, we will assume that all node values are unique. For each node value ~P_x~ we will iterate over all of its multiples ~k \times P_x \le M~ where ~M~ denotes the largest possible node value. For each such multiple, we will find a node with the minimal value larger than or equal to ~x~, and in the case when ~k = 1~, the node with the minimal value strictly larger than ~P_x~. We denote this node with ~y~, and add the corresponding edge to the list of edges we must process.

By doing this, we have at most ~\mathcal O(M \log M)~ edges, which we can use to construct a minimum spanning tree using Kruskal's algorithm. If we naively sort the edges, we will obtain a solution worth ~70\%~ of total points, but since all edge weights are up to ~M~, we can use counting sort and obtain an algorithm in the complexity of ~\mathcal O(N + M \log M)~.

We still have to prove the existence of a minimum spanning tree that holds only the edges that we singled out. Let's assume the contrary, that a tree exists that hold another edge, and has a smaller cost that any other tree that holds only the singled out edges. Let that edge be between nodes ~a~ and ~b~. Let ~P_a < P_b~ and ~k \times P_a \le P_b < (k+1) \times P_a~. Then, since we did not single out that edge, nodes ~c_1, c_2, \dots, c_n~ exist such that it holds ~k \times P_a \le P_{c_1} < P_{c_2} < \dots < P_{c_n} < P_b~, that is ~P_a < P_{c_1} < P_{c_2} < \dots < P_{c_n} < P_b~ if ~k = 1~. But, then we singled out edges ~(a, c_1), (c_1, c_2), (c_2, c_3), \dots, (c_{n-1}, c_n), (c_n, b)~. Their total cost is ~P_b - k \times P_a = P_b \mathbin\% P_a~. However, now we can remove edge ~(a, b)~ and instead of it place a path from ~a~ to ~b~ or some part of it and therefore have a connected graph with smaller or equal weight.