CF2172F Cluster Computing System

ICPC 公司计划建设一个由 $n$ 台服务器组成的集群计算系统。每台服务器都具有一个由正整数表示的数据库协议类型。具体地，第 $i$ 台服务器的协议类型为 $p_i$。 最初，所有服务器都是独立的。公司希望在服务器之间建立连接，使得在最终网络中，每台服务器都可以与任意其他服务器连通（可以直接或间接连通）。 为了实现完全连通，可以建立若干条连接。每次建立连接时，必须选择两台服务器 $u$ 和 $v$（$u < v$）。连接 $u$ 和 $v$ 的费用定义为从 $u$ 到 $v$ 范围内服务器协议类型的最大公约数，即 $gcd(p_u, p_{u+1}, \ldots, p_v)$。 请你计算，为了让所有 $n$ 台服务器都能够互相连通，所需的最小总代价是多少。  这张图是样例输入 2 的示意图。$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$

输出一行一个整数，表示将集群计算系统全部连通所需的最小总代价。

样例 2 说明：图中节点的协议类型分别为 $2$、$4$、$6$、$7$、$14$、$21$。所有可能的连接费用为 $1$、$2$ 或 $7$，由线条粗细区分。存在一种连接方式，通过五条费用为 $1$ 的连接（用红色标出），就能将所有服务器连接起来。 由 ChatGPT 5 翻译