卡片取模生成树(Sirni)

题目描述

本题对应 COCI 2016/2017 Contest #6：Sirni。

给定 $n$ 张卡片，第 $i$ 张卡片上写有一个正整数 $P_i$。

如果你想在卡片 $i$ 和卡片 $j$ 之间建立一条无向连接，所需花费为 $\min(P_i \bmod P_j,\ P_j \bmod P_i)$。

请你求出将全部 $n$ 张卡片连通所需的最小总花费。

输入格式

第一行包含一个正整数 $n$，表示卡片数量。

接下来 $n$ 行，每行一个正整数 $P_i$，表示第 $i$ 张卡片上的数值。

输出格式

输出一行一个整数，表示将所有卡片连通的最小总花费。

样例输入 #1

3
2
6
11

样例输出 #1

1

样例输入 #2

4
2
4
8
11

样例输出 #2

1

样例输入 #3

5
5
8
11
17
23

样例输出 #3

5

数据范围

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le P_i \le 10^7$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

测试点分布

出处：原题链接