#CW70. 公约数(divisor)
公约数(divisor)
题目描述
重新排列只改变元素出现的先后次序;每个输入元素必须且只使用一次。
给定由正整数组成的数组。你可以任意重新排列数组,得到排列 。定义前缀最大公约数 ,其中单个数的最大公约数就是它本身。请最大化 。重新排列可以保持原顺序,也可以完全改变顺序。
输入格式
从 divisor.in 文件中读入。
第一行一个整数 。第二行给出 个正整数 。
输出格式
向 divisor.out 文件中输出。
输出一个整数,表示所有排列中前缀最大公约数总和的最大值。
样例 1 输入
6
2 3 1 2 6 2
样例 1 输出
14
样例 1 解释
一种最优排列为 :前缀 gcd 依次为 ,和为 。
样例 2 输入
10
5 7 10 3 1 10 100 3 42 54
样例 2 输出
131
数据范围
,。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 10 | ||
| 2 | 20 | ||
| 3 | 30 | ||
| 4 | 40 | 完整约束 |