Fishermen

题意翻译

给你一个长度为 $n$ 的序列 $\{a\}$，你可以将 $\{a\}$ 中的数重新排列，并根据重排后的序列 $\{a\}$ 生成序列 $\{b\}$，生成方法如下： - $b_1=a_1$。 - $\forall i\in(1,n]$，$b_i$ 是满足 $a_i|b_i$ 且 $b_i>b_{i-1}$ 的的小正整数。 求所以可能生成的序列 $\{b\}$ 中 $\sum\limits_{i=1}^nb_i$ 的最小值。

题目描述

There are $ n $ fishermen who have just returned from a fishing trip. The $ i $ -th fisherman has caught a fish of size $ a_i $ . The fishermen will choose some order in which they are going to tell the size of the fish they caught (the order is just a permutation of size $ n $ ). However, they are not entirely honest, and they may "increase" the size of the fish they have caught. Formally, suppose the chosen order of the fishermen is $ [p_1, p_2, p_3, \dots, p_n] $ . Let $ b_i $ be the value which the $ i $ -th fisherman in the order will tell to the other fishermen. The values $ b_i $ are chosen as follows: - the first fisherman in the order just honestly tells the actual size of the fish he has caught, so $ b_1 = a_{p_1} $ ; - every other fisherman wants to tell a value that is strictly greater than the value told by the previous fisherman, and is divisible by the size of the fish that the fisherman has caught. So, for $ i > 1 $ , $ b_i $ is the smallest integer that is both strictly greater than $ b_{i-1} $ and divisible by $ a_{p_i} $ . For example, let $ n = 7 $ , $ a = [1, 8, 2, 3, 2, 2, 3] $ . If the chosen order is $ p = [1, 6, 7, 5, 3, 2, 4] $ , then: - $ b_1 = a_{p_1} = 1 $ ; - $ b_2 $ is the smallest integer divisible by $ 2 $ and greater than $ 1 $ , which is $ 2 $ ; - $ b_3 $ is the smallest integer divisible by $ 3 $ and greater than $ 2 $ , which is $ 3 $ ; - $ b_4 $ is the smallest integer divisible by $ 2 $ and greater than $ 3 $ , which is $ 4 $ ; - $ b_5 $ is the smallest integer divisible by $ 2 $ and greater than $ 4 $ , which is $ 6 $ ; - $ b_6 $ is the smallest integer divisible by $ 8 $ and greater than $ 6 $ , which is $ 8 $ ; - $ b_7 $ is the smallest integer divisible by $ 3 $ and greater than $ 8 $ , which is $ 9 $ . You have to choose the order of fishermen in a way that yields the minimum possible $ \sum\limits_{i=1}^{n} b_i $ .

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \le n \le 1000 $ ) — the number of fishermen. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^6 $ ).

输出格式

Print one integer — the minimum possible value of $ \sum\limits_{i=1}^{n} b_i $ you can obtain by choosing the order of fishermen optimally.

输入输出样例

输入样例 #1

7
1 8 2 3 2 2 3

输出样例 #1

33

输入样例 #2

10
5 6 5 6 5 6 5 6 5 6

输出样例 #2

165

**题目大意：**
题目描述了一群渔民捕鱼后对鱼的大小进行报告的情景。渔民们可以将报告的顺序任意排列，并且在报告时可以夸大鱼的实际大小，但是必须保证报告的鱼的大小是实际鱼大小的倍数，并且比前一个渔民报告的鱼的大小要大。要求计算所有可能的报告顺序中，所有鱼的大小总和的最小值。

**输入输出数据格式：**
- **输入格式：**
- 第一行包含一个整数 $ 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 $。

**输入输出样例：**
- **输入样例 #1：**
```
7
1 8 2 3 2 2 3
```
- **输出样例 #1：**
```
33
```

- **输入样例 #2：**
```
10
5 6 5 6 5 6 5 6 5 6
```
- **输出样例 #2：**
```
165
```**题目大意：** 题目描述了一群渔民捕鱼后对鱼的大小进行报告的情景。渔民们可以将报告的顺序任意排列，并且在报告时可以夸大鱼的实际大小，但是必须保证报告的鱼的大小是实际鱼大小的倍数，并且比前一个渔民报告的鱼的大小要大。要求计算所有可能的报告顺序中，所有鱼的大小总和的最小值。 **输入输出数据格式：** - **输入格式：** - 第一行包含一个整数 $ 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 $。 **输入输出样例：** - **输入样例 #1：** ``` 7 1 8 2 3 2 2 3 ``` - **输出样例 #1：** ``` 33 ``` - **输入样例 #2：** ``` 10 5 6 5 6 5 6 5 6 5 6 ``` - **输出样例 #2：** ``` 165 ```