Given a bidirected graph on $n$ vertices ($n\leq10^5$). Each vertex is assigned a value $P_i$ ($1\leq P_i\leq 10^7$). The weight of the edge between $i$ and $j$ equals $\min(P_i\%P_j, P_j\%P_i)$. Find the MST of this graph. The time limit is $1$ second.
If $n\leq10^3$, I can use Kruskal's Algorithm. I don't know why $P_i\leq10^7$. Maybe they let we use a sieve like prime sieve. It's easily to see, we can use all zero-weighted edges.
But now I don't have and efficient approach
Vietnamese Statement and Online Judge (You can see test): http://csloj.ddns.net/problem/1351
First things first, if there are repeated values we can delete the multiples and the answer wont change.
We are going to do kruskal, but some edges don't need to be considered.
For each $a$ we are going to insert some edges $(a,b)$ where $b>a$, such that these edges are enough.
The condition is that in each interval $[ka,ka+a-1)$ we only need to add edges to the smallest value of $b$ in that range (call it $s$), this is because the edges $(a,s),(s,b)$ cost the same as $(a,b)$ but connect more stuff. for values of $a$ larger than $\sqrt{10^7}$ we have at most $\sqrt{10^7}$ neighbours and for values of $a$ smaller than $\sqrt{10^7}$ we have at most $n$ neighbours.
So we expect to insert $n\sqrt{10^7}$ edges, although I think it's a bit less than that, and then one can do Kruskal with the reduced edge list, it could pass since the $\log$ of sort is small, but I'm not sure if it will pass :)
Another optimization you can do is to add all edges of cost $0$ and note that when you are considering the values of $a$, if $a$ is a multiple of another number then you can only consider the edge going from $a$ to the immediate next value.
Here is the submission with $100\%$