CF1728F Fishermen

有 $n$ 个渔夫刚刚结束了一次钓鱼之旅。第 $i$ 个渔夫钓到了一条大小为 $a_i$ 的鱼。 渔夫们将选择一个顺序来依次报出他们钓到的鱼的大小（顺序即为 $n$ 的一个排列）。然而，他们并不完全诚实，他们可能会“夸大”自己钓到的鱼的大小。 具体来说，假设渔夫们选择的顺序为 $[p_1, p_2, p_3, \dots, p_n]$。设 $b_i$ 表示顺序中第 $i$ 个渔夫报出的鱼的大小。$b_i$ 的取值规则如下： - 顺序中的第一个渔夫会如实报出自己钓到的鱼的大小，即 $b_1 = a_{p_1}$； - 其余每个渔夫都希望报出的数值严格大于前一个渔夫报出的数值，并且能被自己钓到的鱼的大小整除。也就是说，对于 $i > 1$，$b_i$ 是满足 $b_i > b_{i-1}$ 且 $a_{p_i} \mid b_i$ 的最小整数。 例如，设 $n = 7$，$a = [1, 8, 2, 3, 2, 2, 3]$。如果选择的顺序为 $p = [1, 6, 7, 5, 3, 2, 4]$，则： - $b_1 = a_{p_1} = 1$； - $b_2$ 是大于 $1$ 且能被 $2$ 整除的最小整数，为 $2$； - $b_3$ 是大于 $2$ 且能被 $3$ 整除的最小整数，为 $3$； - $b_4$ 是大于 $3$ 且能被 $2$ 整除的最小整数，为 $4$； - $b_5$ 是大于 $4$ 且能被 $2$ 整除的最小整数，为 $6$； - $b_6$ 是大于 $6$ 且能被 $8$ 整除的最小整数，为 $8$； - $b_7$ 是大于 $8$ 且能被 $3$ 整除的最小整数，为 $9$。 你需要选择一种渔夫报数的顺序，使得 $\sum\limits_{i=1}^{n} b_i$ 的值尽可能小。

第一行包含一个整数 $n$（$1 \le n \le 1000$），表示渔夫的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）。

输出一个整数，表示通过最优顺序能得到的最小可能的 $\sum\limits_{i=1}^{n} b_i$。

由 ChatGPT 4.1 翻译