98 lines
1.8 KiB
Markdown
98 lines
1.8 KiB
Markdown
# 因子
|
|
|
|
## 题目描述
|
|
|
|
今天是$ YQH $的生日，她得到了一个长度为$ n $的正整数序列$ a_1,a_2,\dots,a_n $作为生日礼物。
|
|
|
|
然而，$YQH $并不对这个序列满意，因为这个序列可能不合法。
|
|
|
|
具体地，一个序列合法，当且仅当存在一个大于$ 1 $的整数$ k$，使得序列里每个元素都是$ k $的倍数。
|
|
|
|
为了让$ YQH $满意，你需要找到一个$ a_1,a_2,\dots,a_n $的子序列，使得这个子序列是合法的。$b_1,b_2,\dots,b_m $称为$ a_1,a_2,\dots,a_n $的子序列当且仅当，你可以从$ a_1,a_2,\dots,a_n $删去若干个（可以是$ 0 $个）元素后得到$ b_1,b_2,\dots,b_m$。
|
|
|
|
符合条件的子序列可能很多，所以$ YQH $只想要你找到，总和最大的合法子序列的总和。注意，子序列可以取空集，且空集是合法的。
|
|
|
|
## 输入格式
|
|
|
|
第一行一个正整数$ n$。
|
|
|
|
接下来$ n $行，每行一个正整数。第$ i $行的数表示$ a_{i-1}$。
|
|
|
|
## 输出格式
|
|
|
|
输出一个整数表示答案。
|
|
|
|
## 样例 #1
|
|
|
|
### 样例输入 #1
|
|
|
|
```
|
|
4
|
|
1
|
|
1
|
|
1
|
|
1
|
|
```
|
|
|
|
### 样例输出 #1
|
|
|
|
```
|
|
0
|
|
```
|
|
|
|
## 样例 #2
|
|
|
|
### 样例输入 #2
|
|
|
|
```
|
|
6
|
|
1
|
|
2
|
|
3
|
|
4
|
|
5
|
|
6
|
|
```
|
|
|
|
### 样例输出 #2
|
|
|
|
```
|
|
12
|
|
```
|
|
|
|
## 样例 #3
|
|
|
|
### 样例输入 #3
|
|
|
|
```
|
|
10
|
|
28851
|
|
8842
|
|
9535
|
|
2311
|
|
25337
|
|
26467
|
|
12720
|
|
10561
|
|
8892
|
|
6435
|
|
```
|
|
|
|
### 样例输出 #3
|
|
|
|
```
|
|
56898
|
|
```
|
|
|
|
## 提示
|
|
|
|
| 子任务编号 | $n\le$ | $a_i\le $| 特殊限制 | 分值 |
|
|
| :--------: | :--: | :----: | :------: | :--: |
|
|
| 1 | $18 $ | $10^9 $ | 无 | 20 |
|
|
| 2 | $1000$ | $10^5 $ | 无 | 20 |
|
|
| 3 | $1000$| $10^9 $ | A | 20 |
|
|
| 4 | $1000$ | $10^9$ | 无 | 40 |
|
|
|
|
特殊限制$A$：保证所有$ a_i $都是质数。
|
|
|
|
对于所有数据，保证$ 1\le n\le 1000,1\le a_i\le 10^91\le n\le 1000,1\le a_i\le 10^9$。 |