codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/189a46042fce470399ad63f516932e11eeae46e5.png) 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).