小红很喜欢 gcd 和 sum。 小红定义一个长度为 的数组 的权值为 。 现在小芳给了小红一个长度为 的数组 ，小红可以从中挑选一个子序列带走。请你帮小红求出她能带走的权值最大的非空子序列。 【名词解释】 ：即求解 的最大公约数，指所有整数共有约数中最大的一个。例如，、 和 的公约数有 ，其中最大的约数是 ，因此 。 非空子序列：从原序列中删除任意个（可以为零，但必须保留至少一个）元素后，保持剩余元素相对顺序不变得到的新序列。
输入描述:
第一行输入一个整数 ，代表数组的长度。第二行输入  个整数 ，表示数组中的元素。


输出描述:
输出一个整数，代表权值最大子序列的权值。
示例1

输入

3
2 6 4

输出

36

说明

\hspace{15pt}在这个样例中，一共有 7 种不同的子序列选择方案：
\hspace{23pt}\bullet\,\{2\}，权值为 2\times 2=4；
\hspace{23pt}\bullet\,\{6\}，权值为 6\times 6=36；
\hspace{23pt}\bullet\,\{4\}，权值为 4\times 4=16；
\hspace{23pt}\bullet\,\{2,6\}，权值为 \operatorname{gcd}(2,6)\times (2+6)=2\times 8=16；
\hspace{23pt}\bullet\,\{2,4\}，权值为 \operatorname{gcd}(2,4)\times (2+4)=2\times 6=12；
\hspace{23pt}\bullet\,\{6,4\}，权值为 \operatorname{gcd}(6,4)\times (6+4)=2\times 10=20；
\hspace{23pt}\bullet\,\{2,6,4\}，权值为 \operatorname{gcd}(2,6,4)\times (2+6+4)=2\times 12=24。
\hspace{15pt}综上，权值最大的子序列是 \{6\}，权值为 36。
示例2

输入

6
1 1 4 5 1 4

输出

32

说明

\hspace{15pt}在这个样例中，选择 \{4,4\} 是最优的。

备注:
本题已于下方时间节点更新，请注意题解时效性：1. 2025-12-10 增加若干组数据。
加载中...