← 返回题目列表

Codeforces · 2172/F

F. 集群计算系统

中文机器翻译题面 查看原题

ICPC公司计划构建一个由$$$n$$$服务器组成的集群计算系统。每个服务器都有一个 数据库协议类型 用正整数表示。具体来说,第$$$i$$$服务器具有协议类型$$$p_i$$$。

最初,所有服务器都是独立的。该公司希望在服务器之间建立连接,以便在最终的网络中,每台服务器都可以(直接或间接)到达其他服务器。

要实现完全连接,您可以建立多个连接。每次建立连接时,必须选择两个服务器$$$u$$$ 和$$$v$$$ ($$$u \lt v$$$)。在 $$$u$$$ 和 $$$v$$$ 之间建立连接的成本定义为 通用协议 $$$u$$$ 到 $$$v$$$ 范围内的数据库的 ,计算公式为 $$$\gcd(p_u, p_{u+1}, \ldots, p_v)$$$ $$$^{\text{*}}$$$。

确定完全连接所有 $$$n$$$ 服务器所需的最低总成本,以便每个服务器都可以从其他服务器访问。

示例输入 2 的插图。

$$$^{\text{*}}$$$$$$\mathrm{gcd}$$$ 是除该集合中的每个整数而不留下余数的最大正整数。

输入

第一行包含一个整数$$$n$$$,表示服务器的数量。

第二行包含$$$n$$$正整数$$$p_1, p_2, \ldots, p_n$$$,其中$$$p_i$$$是第$$$i$$$服务器的数据库协议类型。

  • $$$2\leq n\leq 2\times 10^5$$$
  • $$$1\leq p_i \leq 10^9$$$

输出

一行输出单个整数,代表完全连接集群计算系统所需的最小总成本。

示例

输入
复制

3
4 2 6

输出
复制

4

输入
复制

6
2 4 6 7 14 21

输出
复制

5

注意

例2说明: 该图显示了协议类型 $$$2$$$、$$$4$$$、$$$6$$$、$$$7$$$、$$$14$$$ 和 $$$21$$$ 的示例。所有可能连接的成本为 $$$1$$$、$$$2$$$ 或 $$$7$$$,由不同的宽度表示。有一种方法可以将所有连接连接在一起,每个连接的成本为 $$$1$$$(显示为红色)。