I sometimes make problems and post them in Japanese local contest yukicoder. I want many people to know math problems I made, so I introduce some of them. Let's try!!

LCMST

Problem Statement

Consider a complete graph $$$G$$$ on $$$N$$$ vertices. The weight of edge between vertex $$$i$$$ and $$$j$$$ is least common multiple of $$$A_i$$$ and $$$A_j$$$. Find the total weight of the edges contained in a minimum spanning tree of $$$G$$$.

Constraints

• $$$2\leq N \leq 10^6$$$
• $$$1\leq A_i\leq 10^5$$$
• Time Limit is 4000ms

Sample

When $$$N=3$$$ and $$$A=(2,3,4)$$$, the answer is 10. This is optimal to draw edges between $$$(1,2),(1,3)$$$. These have weights $$$\mathrm{lcm}(A_1,A_2)=\mathrm{lcm}(2,3)=6, \mathrm{lcm}(A_1,A_3)=\mathrm{lcm}(2,4)=4$$$, respectively.

Hints