408062: GYM102968 L Yet another roads problem

Following a narrative plot that you have never encountered in any other programming contest before, you are the Ministry of Transport in country Foo. This realm's historical context led to all of the cities being secluded from each other. Although the country is doing amazing as it is, we would not have a problem statement without changing something.

Therefore, I have now decided that the country is doing horrible, and the reason why is that you cannot move from a city to another. The solution is simple: just build roads.

Although you could simply build roads between all cities and call it a day, there is a plot twist - the country is poor$$$^{TM}$$$. Therefore the number of roads built must be minimized, while also ensuring that citizens can travel from any city to another.

In addition, building a road between two cities will contribute to Foo's economic growth. For inexplicable reasons, this growth is given by the greatest common divisor of the two cities' number of residents.

Given the number of cities, $$$N$$$, and the number of residents of every single one of them, $$$x_i$$$ ($$$1\leq i \leq N$$$), it is asked of you to build a minimum amount of roads such that you can travel from any city to another, while also maximizing the total economic growth.

The first line consists of an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of cities. The second line will contain $$$N$$$ other integers $$$x_i$$$ ($$$1 \leq x_i \leq 10^6$$$), where $$$x_i$$$ denotes the number of residents of city $$$i$$$.

It is asked of you to print an integer which represents the total economic growth of country Foo after building all of the roads. Bear in mind that it must be maximized.

7
42 21 5 6 7 3 9

41

A road can be built between the first two cities, generating an economic growth of 21. Connecting the first city to the 4$$$^{th}$$$ and 5$$$^{th}$$$ ones will further increase the total growth by 6, respectively 7. Moreover, building a road between the last two cities will contribute to the growth by a value of 3. To make all cities reachable from one another, we now build a road between the first and last city, growing the economy by 3, and from the third to whichever city, increasing the total growth by 1.

Therefore we get a total economic growth of $$$21+7+6+3+3+1=41$$$.