公式解説における \(D _ g\) の値や \(g\times D _ g\) の値を、\(O(N+M\log\log M)\) 時間で求めることができます。

\(i=1,2,\ldots,M\) に対して \(C _ i\) の値が得られているとき、\(\displaystyle D _ g=\sum _ {g|i}C _ i\) の値を \(g=1,2,\ldots,M\) のすべてに対して求めることは \(O(M\log\log M)\) 時間でできることが知られています。 詳細は 高速ゼータ変換の約数版 O(N log(log(N))) - noshi91のメモ などを参考にしてください。

このアルゴリズムを少し変形することで直接 \(g\times D _ g\) の値を求めることもできます。

実装例は以下のようになります。

#include <iostream>
#include <array>
#include <bitset>
#include <algorithm>
using namespace std;

int main(){
    constexpr int max_A{1000000};
    array<long, max_A + 1> count{};
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        count[A] += A;
    }

    bitset sieve = ~bitset<max_A + 1>{}; // エラトステネスの篩
    for (int p = 2; p <= max_A; ++p) if (sieve[p]) {
        for (int i = max_A / p + 1; i--;) { // 逆順に累積和を取る
            sieve[i * p] = false;
            count[i] += count[i * p] / p;
        }
    }
    cout << ranges::max(count) << endl; // 最大値を出力
    return 0;
}