15206번 - GCD-sum 다국어

A multi-set (i.e. a set with possible repetitions) of $n$ integers is given. We split the set into $k$ disjoint groups, for every group we compute the greatest common divisor of its elements, and sum all the subsets' GCDs.

For every $k = 1, 2, \ldots, n$, determine the maximal sum which can be obtained this way

In the first line of input there is a single integer $n$ ($1 \leq n \leq 500\,000$) -- the cardinality of the set. In the second line, there are $n$ positive integers, not exceeding $10^{12}$ -- the given sequence.

Output $n$ line scontaining one integer each -- the best sum of GCDs when partitioning into $1$, $2$, $\ldots$, $n$ subsets.

For $k = 2$, the best partition is $(10,10)$ and $(9,3)$, giving the sum of $10+3 = 13$. For $k=3$, the best partition is $(10)$, $(10)$ and $(9,3)$ with the sum of $23$.