1.8 KiB
1.8 KiB
因子
题目描述
今天是$ 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$。