小红与gcd和sum
题号：NC295920
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小红很喜欢 gcd 和 sum。
\hspace{15pt}小红定义一个长度为 k 的数组 \{a_1,a_2,\dots,a_k\} 的权值为 \textstyle\operatorname{gcd}(a_{1},a_{2},\dots,a_{k})~\times~(a_1+a_2+\dots+a_k) 。
\hspace{15pt}现在小芳给了小红一个长度为 n 的数组 \{a_1,a_2,\dots,a_n\}，小红可以从中挑选一个子序列带走。请你帮小红求出她能带走的权值最大的非空子序列。

【名词解释】
\hspace{15pt}\operatorname{gcd}(a_1,a_2,\dots,a_k)：即求解 a_1,a_2,\dots,a_k 的最大公约数，指所有整数共有约数中最大的一个。例如，12、18 和 30 的公约数有 1,2,3,6，其中最大的约数是 6，因此 \operatorname{gcd}(12,18,30)=6。
\hspace{15pt}非空子序列：从原序列中删除任意个（可以为零，但必须保留至少一个）元素后，保持剩余元素相对顺序不变得到的新序列。

输入描述:

\hspace{15pt}第一行输入一个整数 n\left(1\leqq n \leqq 10^5\right)，代表数组的长度。
\hspace{15pt}第二行输入 n 个整数 a_{1},a_{2},\dots,a_{n}\left(1 \leqq a_{i} \leqq 10^6\right)，表示数组中的元素。

输出描述:

\hspace{15pt}输出一个整数，代表权值最大子序列的权值。
示例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 增加若干组数据。