题意：

重排数组，使得 \(\sum \limits _{i=1}^n \gcd (a_1,a_2,\cdots a_i)\) 最大。输出最大值。

\(n\le 1e5,1\le a_i \le 5e6\)

思路：

\(dp[x]\) 表示以 \(x\) 为第一个数的最大值。那么 \(dp[x]\) 和 \(dp[y]\)（\(y\) 是 \(x\) 的因子）之间有什么关系呢？对于所有 \(x\) 的倍数和所有 \(y\) 的倍数，把所有 \(x\) 的倍数放在前面，把是 \(y\) 的倍数但不是 \(x\) 的倍数的数放在后面是最优的，即形如 \(x,2x,3x,\cdots,nx,y,2y,3y,\cdots ,my\) 。

记 \(S_x\) 为所有 \(x\) 的倍数的集合， \(S_y\) 为所有 \(y\) 的倍数的集合，则 \(S_x\subset S_y\)。那么 \(dp[x]=dp[y] + |S_x|(x- y)\)

实际跑了3500ms，勉强能过。。。

const int N = 5e6 + 5;
ll n, cnt[N], dp[N];

signed main()
{
    cin >> n;
    for(int i = 1, x; i <= n; i++)
    {
        cin >> x;
        cnt[x]++;
    }

    for(int i = 1; i < N; i++)
        for(int j = i + i; j < N; j += i)
            cnt[i] += cnt[j];

    dp[1] = n;
    for(int i = 1; i < N; i++)
        for(int j = i + i; j < N; j += i)
            dp[j] = max(dp[j], dp[i] + cnt[j] * (j - i));

    cout << *max_element(dp + 1, dp + N);

    return 0;
}