#CW70. 公约数(divisor)

公约数(divisor)

题目描述

重新排列只改变元素出现的先后次序;每个输入元素必须且只使用一次。

给定由正整数组成的数组。你可以任意重新排列数组,得到排列 b1,b2,…,bnb_1,b_2,\dots,b_n。定义前缀最大公约数 gi=gcd⁡(b1,b2,…,bi)g_i=\gcd(b_1,b_2,\dots,b_i),其中单个数的最大公约数就是它本身。请最大化 g1+g2+⋯+gng_1+g_2+\dots+g_n。重新排列可以保持原顺序,也可以完全改变顺序。

输入格式

从 divisor.in 文件中读入。

第一行一个整数 nn。第二行给出 nn 个正整数 a1,a2,…,ana_1,a_2,\dots,a_n。

输出格式

向 divisor.out 文件中输出。

输出一个整数,表示所有排列中前缀最大公约数总和的最大值。

样例 1 输入

6
2 3 1 2 6 2

样例 1 输出

14

样例 1 解释

一种最优排列为 6,2,2,2,3,16,2,2,2,3,1:前缀 gcd 依次为 6,2,2,2,1,16,2,2,2,1,1,和为 1414。

样例 2 输入

10
5 7 10 3 1 10 100 3 42 54

样例 2 输出

131

数据范围

1≤n≤1051\le n\le 10^5,1≤ai≤2×1071\le a_i\le 2\times 10^7。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 10 1∼51\sim 5 n≤16n\le 16
2 20 6∼106\sim 10 max⁡ai≤5000\max a_i\le 5000
3 30 11∼1511\sim 15 max⁡ai≤106\max a_i\le 10^6
4 40 16∼2016\sim 20 完整约束