Divan and Kostomuksha (easy version) (Codeforces 1614D1)
Tags: DP, number theory

This is the easy version of the problem. The only difference is maximum value of $$$a_i$$$.Once in Kostomuksha Divan found an array $$$a$$$ consisting of positive integers. Now he wants to reorder the elements of $$$a$$$ to maximize the value of the following function: $$$$$$\sum_{i=1}^n \operatorname{gcd}(a_1, \, a_2, \, \dots, \, a_i),$$$$$$ where $$$\operatorname{gcd}(x_1, x_2, \ldots, x_k)$$$ denotes the greatest common divisor of integers $$$x_1, x_2, \ldots, x_k$$$, and $$$\operatorname{gcd}(x) = x$$$ for any integer $$$x$$$.Reordering elements of an array means changing the order of elements in the array arbitrary, or leaving the initial order.Of course, Divan can solve this problem. However, he found it interesting, so he decided to share it with you.

Input: The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the size of the array $$$a$$$.The second line contains $$$n$$$ integers $$$a_{1}, \, a_{2}, \, \dots, \, a_{n}$$$ ($$$1 \le a_{i} \le 5 \cdot 10^6$$$) — the array $$$a$$$.

Output: Output the maximum value of the function that you can get by reordering elements of the array $$$a$$$.

Note: In the first example, it's optimal to rearrange the elements of the given array in the following order: $$$[6, \, 2, \, 2, \, 2, \, 3, \, 1]$$$:$$$$$$\operatorname{gcd}(a_1) + \operatorname{gcd}(a_1, \, a_2) + \operatorname{gcd}(a_1, \, a_2, \, a_3) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5, \, a_6) = 6 + 2 + 2 + 2 + 1 + 1 = 14.$$$$$$ It can be shown that it is impossible to get a better answer.In the second example, it's optimal to rearrange the elements of a given array in the following order: $$$[100, \, 10, \, 10, \, 5, \, 1, \, 3, \, 3, \, 7, \, 42, \, 54]$$$.

Sample Inputs:
6
2 3 1 2 6 2

10
5 7 10 3 1 10 100 3 42 54

Sample Outputs:
14

131

Solution (Python):
m = 5 * 10 ** 6 * +1
eratosthenes = [-1] * (m + 1)
for i in range(2, m + 1):
    if eratosthenes[i] == -1:
        eratosthenes[i] = i
        j = 2
        while i * j <= m:
            eratosthenes[i * j] = i
            j += 1
import collections

def fact(n):
    c = []
    while n != 1:
        k = eratosthenes[n]
        c.append(k)
        n //= k
    return collections.Counter(c)

def div(n):
    s = [1]
    while n != 1:
        p = eratosthenes[n]
        cnt = 1
        n //= p
        while eratosthenes[n] == p:
            cnt += 1
            n //= p
        t = s.copy()
        for i in t:
            for j in range(1, cnt + 1):
                s.append(i * p ** j)
    return s
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
mx = max(a)
cnt = [0] * (mx + 1)
for i in c:
    j = c[i]
    for k in div(i):
        cnt[k] += j
dp = [0] * (mx + 1)
dp[1] = n
for i in range(2, mx + 1):
    if cnt[i] == 0:
        continue
    for j in div(i):
        if cnt[j] != 0 and i != j:
            dp[i] = max(dp[i], dp[j] + (i - j) * cnt[i])
print(max(dp))

Solution (Python):
import collections as C
N = 5000001
(c, e, P, v, d) = (C.Counter(list(map(int, [*open(0)][1].split()))), [0] * N, [0], [0] * N, [0] * N)
for i in range(2, N):
    if e[i] < 1:
        P.append(i)
        j = i
        while j < N:
            e[j] = i
            j += i

def f(n):
    s = [1]
    while n > 1:
        (p, c, w) = (e[n], 1, [])
        while e[n] == p:
            c += 1
            n //= p
        for g in s:
            for i in range(c):
                w.append(g * p ** i)
        s = w
    return s
for i in c:
    for j in f(i):
        v[j] += c[i]
i = N
while i > 1:
    i -= 1
    if v[i] > 0:
        for p in P:
            if p * i >= N:
                break
            d[i] = max(d[i], d[p * i] + i * (v[i] - v[p * i]))
print(d[1])

Solution (Python):
import collections
n = int(input())
a = list(map(int, input().split()))
size = 5000001
import time
era = [0] * size
primes = []
for i in range(2, size):
    if era[i] == 0:
        primes.append(i)
        for j in range(i, size, i):
            era[j] = i
count = collections.Counter(a)

def fact(n):
    s = [1]
    while n > 1:
        p = era[n]
        count = 0
        while n % p == 0:
            count += 1
            n //= p
        new = []
        for guy in s:
            for i in range(count + 1):
                new.append(guy * p ** i)
        s = new
    return s
divs = [0] * size
tot = 0
for i in count:
    l = fact(i)
    tot += len(l)
    for j in l:
        if j < size:
            divs[j] += count[i]
dp = [0] * size
for i in range(size - 1, 0, -1):
    if divs[i] > 0:
        dp[i] = i * divs[i]
        for p in primes:
            j = p * i
            if j >= size:
                break
            dp[i] = max(dp[i], dp[j] + i * (divs[i] - divs[j]))
print(dp[1])