Subtask 1: ~n \le 20, a_i \le 10^6~.

Duyệt nhị phân mọi tập con. Nếu ước chung lớn nhất của tập con đó khác ~1~, ta sẽ cập nhật kết quả.

Độ phức tạp: ~O~ (~2^n \times log_{2}~ ~a_i~).

Subtask 2: ~n \le 20~.

Lúc này, kết quả có thể lớn hơn ~10^{19}~. Có thể sử dụng bignum, tuy nhiên trong quá trình tính toán, ta chỉ sử dụng phép cộng, nên ta có thể lưu bignum dưới dạng ~{x, y}~ với ý nghĩa: giá trị thực của số ta lưu là ~10^{18} \times x + y~.

Độ phức tạp: ~O~ (~2^n \times log_{2}~ ~a_i~).

Subtask 3: ~n \le 40~.

Thay vì duyệt mọi tập con, ta có thể chia đôi tập để giảm độ phức tạp.

Độ phức tạp: ~O~ (~2^{\frac {n}{2}} \times log_{2}~ ~a_i~).

Subtask 4: ~a_i \le 1000~.

Duyệt ~val~ từ ~1~ tới ~n~, với ý nghĩa ta đang thử chia đều số kẹo cho ~val~ nhóm.

Với mỗi giá trị ~val~ từ ~1~ tới ~n~, kết quả sẽ là tổng các số chia hết cho ~val~. Từ đó, dễ dàng cập nhật vào kết quả.

Độ phức tạp: ~O~ (~1000 \times n~).

Subtask 5, 6: ~a_i \le 10^9~.

Nhận xét: Ta chỉ quan tâm ~val~ là số nguyên tố. Vì vậy, ~val~ chỉ có thể là các ước nguyên tố của ~a_i~. Một số ~\le 10^9~ có tối đa ~10~ ước nguyên tố khác nhau. Ta có thể phân tích một số ra thừa số nguyên tố với độ phức tạp ~O~ (~\sqrt n~).

Với mỗi giá trị ~val~, kết quả sẽ là tổng các số chia hết cho ~val~. Từ đó, dễ dàng cập nhật vào kết quả.

Độ phức tạp: ~O~ (~\sqrt a_i \times n~).

Subtask 7: ~a_i~ là số nguyên tố.

Với subtask này, không số nào có ước chung với bất kỳ số nào, trừ trường hợp chúng bằng nhau hoàn toàn. Vì vậy, kết quả là ~\max cnt_{a_i} \times a_i~, với ~cnt_x~ là số lần xuất hiện giá trị ~x~ trong dãy.

Độ phức tạp: ~O~ (~n \times log_2~ ~n~).

Subtask 8, 9: ~n \le 2000~.

Ta cần một cách lấy ra mọi ước nguyên tố của ~a_i \le 10^{18}~.

Trước hết, ta sẽ loại bỏ mọi ước nguyên tố ~\le 10^6~ của ~a_i~. Từ ~1~ tới ~10^6~ chỉ có ~50000~ số nguyên tố, nên dễ dàng duyệt qua mọi số nguyên tố và chia dần.

Định nghĩa: Phần lẻ của ~a_i~ là phần còn lại của số ~a_i~ sau khi bỏ hết các thừa số nguyên tố ~\le 10^6~.

Đến đây, phần lẻ này chỉ có hai dạng:

• Trường hợp 1: Phần lẻ đó là một số nguyên tố
• Trường hợp 2: Phần lẻ đó là tích của hai số nguyên tố (không nhất thiết phân biệt).

Nếu như phần lẻ này là tích của ba số nguyên tố trở lên, mà các số nguyên tố này đều ~> 10^6~ như định nghĩa, thì số này sẽ ~> 10^{18}~, vi phạm giả thiết đề bài.

Ta có thể phân tách hai trường hợp này bằng cách kiểm tra số nguyên tố Rabin Milner.

• Trường hợp 1: Phần lẻ đó là số nguyên tố

Nếu phần lẻ đó là số nguyên tố, ta sẽ duyệt qua mọi số ~a_i~ khác, xem có số nào chia hết cho phần lẻ này không. Cập nhật kết quả là tổng các phần tử chia hết cho phần lẻ này.

• Trường hợp 2: Phần lẻ đó là tích của hai số nguyên tố

Ta sẽ duyệt qua mọi số ~a_i~, và xem có số nào khác ~a_i~, và có ước chung với phần lẻ khác 1.

Nếu như tồn tại một số ~a_i~ thỏa mãn, ta sẽ tách được phần lẻ đó thành tích hai số nguyên tố. Vì vậy, theo Nhận xét 1, dễ dàng cập nhật vào kết quả.

Ngược lại, nếu không tồn tại số ~a_i~ nào thỏa mãn, thì ta duyệt qua mọi ~a_i~, và xem có bao nhiêu số chia hết cho phần lẻ đó, từ đó cập nhật vào kết quả.

Độ phức tạp: ~O~ (~n^2 \times log n~ + ~n \times 50000~).

Code mẫu:

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"

const int N = 1e6 + 9;

const int inf = 1e18;

int n, a[N];

int gcd (int A, int B){
    while (A * B != 0){
        if (A >= B) A %= B;
        else B %= A;
    }
    return A + B;
}

int POW (int a, int b, int p){
    a %= p;
    if (a == 0) return 0;
    int ret = 1;
    while (b > 0){
        if (b & 1){
            ret = (ret * a) % p; b--;
        }
        a *= a; a %= p; b >>= 1;
    }
    return ret;
}

bool checkk (int n, int a, int d, int s){
    int x = POW (a, d, n);
    if (x == 1 || x == n - 1) return 0;
    for (int r = 1; r < s; r++){
        x = x * x % n;
        if (x == n - 1) return 0;
    }
    return 1;
}

bool primecheck (int n){
    if (n < 2) return 0;
    int r = 0, d = n - 1;
    while ((d & 1) == 0){
        d >>= 1;
        r++;
    }
    for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}){
        if (n == a) return 1;
        if (checkk (n, a, d, r)) return 0;
    }
    return 1;
}

struct bigint {
    int x = 0; 
    int y = 0;
    // x * 1e18 + y;

    bigint (): x (0), y (0){}
    bigint (int _x, int _y): x (_x), y (_y){}

    bool operator < (bigint o) const {
        if (x != o.x) return x < o.x;
        return y < o.y;
    }

    bool operator > (bigint o) const {
        if (x != o.x) return x > o.x;
        return y > o.y;
    }

    friend bigint operator + (bigint A, bigint B){
        bigint res;
        res.x = A.x + B.x;
        res.y = A.y + B.y;
        while (res.y >= inf){
            res.x++; res.y -= inf;
        }
        return res;
    }  
};

bigint multiply (bigint a, int b){
    bigint res = {0, 0};
    while (b--) res = res + a;
    return res;
}

string sum (string str1, string str2){
    if (str1.size () > str2.size ()) swap (str1, str2);
    string str = "";
    int n1 = str1.size (), n2 = str2.size ();
    reverse(str1.begin (), str1.end ());
    reverse(str2.begin (), str2.end ());
    int carry = 0;
    for (int i = 0; i < n1; i++){
        int sum = ((str1[i] - '0') + (str2[i] - '0') + carry);
        str.push_back (sum % 10 + '0');
        carry = sum / 10;
    }
    for (int i = n1; i < n2; i++){
        int sum = ((str2[i] - '0') + carry);
        str.push_back (sum % 10 + '0');
        carry = sum / 10;
    }
    if (carry) str.push_back (carry + '0');
    reverse (str.begin (), str.end ());
    string str222 = "";
    bool check = 0;
    for (char i : str){
        if (i == '0'){
            if (check) str222 = str222 + i;
        } else {
            str222 = str222 + i;
            check = 1;
        }
    }
    return str222;
}

int p[N];
vector <int> primes;

void sieve (){
    for (int i = 2; i < N; i++) p[i] = i;
    for (int i = 2; i * i < N; i++) if (p[i] == i) for (int j = i * i; j < N; j += i){
        p[j] = min (p[j], i);
    }
    primes.push_back (2);
    for (int i = 3; i < N; i += 2) if (p[i] == i) primes.push_back (i);
}

int org[N];
map <int, int> cnt_in_array;
bigint cnt_small[N];

signed main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);
    if (fopen ("input.txt", "r")){
        freopen ("input.txt", "r", stdin);
        freopen ("output.txt", "w", stdout);
    }
    sieve ();
    cin >> n;
    bigint res = {0, 0};
    for (int i = 1; i <= n; i++){
        cin >> a[i]; org[i] = a[i];
        cnt_in_array[a[i]]++;
        bigint tmp = multiply ({0, a[i]}, cnt_in_array[a[i]]);
        if (res < tmp) res = tmp;
    }
    // solve for small divisors
    for (int i = 1; i <= n; i++){
        for (int j : primes){
            if (a[i] % j != 0) continue;
            cnt_small[j] = cnt_small[j] + bigint (0, org[i]);
            if (res < cnt_small[j]) res = cnt_small[j];
            while (a[i] % j == 0) a[i] /= j;
        }
    }
    // solve when left is prime
    for (int i = 1; i <= n; i++){
        if (a[i] == 1) continue;
        bigint tmp = {0, 0};
        for (int j = 1; j <= n; j++){
            if (gcd (a[i], a[j]) != 1) tmp = tmp + bigint (0, org[j]);
        }
        if (res < tmp) res = tmp;
    }
    // solve when left is product of 2 primes
    vector <int> has_primes;
    for (int i = 1; i <= n; i++){
        if (a[i] == 1) continue;
        int x = sqrt (a[i]);
        if (x * x == a[i]){
            has_primes.push_back (x);
            continue;
        }
        for (int j = 1; j <= n; j++){
            if (a[j] == a[i]) continue;
            int p = gcd (a[i], a[j]);
            if (p == 1) continue;
            has_primes.push_back (p);
            has_primes.push_back (a[i] / p);
            break;
        }
    }
    map <int, int> processed;
    for (int i : has_primes){
        if (i == 1) continue;
        if (processed[i]) continue;
        processed[i] = 1;
        bigint tmp = {0, 0};
        for (int j = 1; j <= n; j++){
            if (a[j] % i == 0) tmp = tmp + bigint (0, org[j]);
        }
        if (res < tmp) res = tmp;
    }
    string finalres = "0";
    while (res.x--) finalres = sum (finalres, to_string (inf));
    finalres = sum (finalres, to_string (res.y));
    cout << finalres;
}