2172F.md (2216B)
1 Source: https://codeforces.com/problemset/problem/2172/F 2 3 F. Cluster Computing System 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 The ICPC company plans to build a cluster computing system consisting of $n$ servers. Each server has a database protocol type represented by a positive integer. Specifically, the $i$-th server has a protocol type $p_i$. 22 23 Initially, all servers are independent. The company wants to establish connections between servers so that, in the resulting network, every server can reach every other server (either directly or indirectly). 24 25 To achieve full connectivity, you may establish several connections. Each time you establish a connection, you must choose two servers $u$ and $v$ ($u \lt v$). The cost of establishing the connection between $u$ and $v$ is defined as the common protocol of the databases in the range from $u$ to $v$, calculated as $\gcd(p_u, p_{u+1}, \ldots, p_v)$ $^{\text{∗}}$. 26 27 Determine the minimum total cost required to fully connect all $n$ servers so that every server is reachable from every other server. 28 29  An illustration for sample input 2. 30 31 $^{\text{∗}}$$\mathrm{gcd}$ is the largest positive integer that divides every integer in that set without leaving a remainder. 32 33 Input 34 35 The first line contains a single integer $n$, representing the number of servers. 36 37 The second line contains $n$ positive integers $p_1, p_2, \ldots, p_n$, where $p_i$ is the database protocol type of the $i$-th server. 38 39 * $2\leq n\leq 2\times 10^5$ 40 * $1\leq p_i \leq 10^9$ 41 42 Output 43 44 Output a single integer in a line, representing the minimum total cost required to fully connect the cluster computing system. 45 46 Examples 47 48 Input 49 50 ``` 51 3 52 4 2 6 53 ``` 54 55 Output 56 57 ``` 58 4 59 ``` 60 61 Input 62 63 ``` 64 6 65 2 4 6 7 14 21 66 ``` 67 68 Output 69 70 ``` 71 5 72 ``` 73 74 Note 75 76 Explanation of Example 2: The figure shows an example with protocol types $2$, $4$, $6$, $7$, $14$, and $21$. The costs of all possible connections are $1$, $2$, or $7$, indicated by different widths. There is a way to connect all together with five connections of cost $1$ each (displayed in red).