Introduce my masterpieces of math problem

Revision en3, by toam, 2023-02-10 09:58:25

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

Hint1
Hint2
Hint3

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English toam 2023-02-10 11:09:35 11 (published)
en7 English toam 2023-02-10 11:07:15 878 Tiny change: '</spoiler>' -> '</spoiler>\n<spoiler summary="Hint2">\nBinary search\n</spoiler>'
en6 English toam 2023-02-10 10:51:19 1020 Tiny change: 'ditions:\n- There ' -> 'ditions:\n\n- There '
en5 English toam 2023-02-10 10:41:50 935 Tiny change: '-\{(k^2-1)%a\}}{a}$\' -> '-\{(k^2-1)\%a\}}{a}$\'
en4 English toam 2023-02-10 10:19:42 568 Tiny change: '\ 10^9+7$.' -> '\ 10^9+7$. You have $T$ test cases to solve.'
en3 English toam 2023-02-10 09:58:25 1104 Tiny change: 'g tree of the graph.' -> 'g tree of $G$.'
en2 English toam 2023-02-10 09:17:17 70
en1 English toam 2023-02-10 09:15:35 232 Initial revision (saved to drafts)