$O(NlogN)$ 枚举

关键观察：

单元素子序列的权值即为该元素的平方（因为 gcd 为元素本身，和为元素本身）。

多元素子序列的权值受 gcd 和和的影响，gcd 会减小而和会增加，需要权衡。

数学性质：

对于多元素子序列，gcd 是所有元素的公约数，因此可以枚举可能的 gcd 值。

对于每个可能的 gcd 值 $d$ ，收集所有能被 $d$ 整除的元素，计算它们的和 $sum$ ，然后权值为 $d × sum$。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 1e6 + 10, M = 30;

int n;
LL a[N], cnt[N];

void solve() 
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        cnt[a[i]] ++;
    }
    
    LL ans = 0;
    for(int i = 1; i < N; i ++)
    {
        if(cnt[i] == 0) continue;
        
        LL sum = 0;
        for(int j = i; j < N; j += i)
            sum += cnt[j] * j;
        ans = max(ans, sum * i);
    }
    cout << ans << endl;
}            

int main()
{
    int t = 1;
    // cin >> t;
    while(t --)
        solve();
}