CF 1614D1 - Divan and Kostomuksha (easy version)

Rating: 2100
Tags: dp, number theory
Solve time: 1m 35s
Verified: no

Solution

Problem Understanding

We are given a list of positive integers, and we are allowed to reorder them arbitrarily. After fixing an order, we look at all prefixes of this order. For each prefix, we compute the greatest common divisor of all elements in that prefix, and we sum these gcd values over all prefixes. The task is to choose the permutation that maximizes this sum.

The key object is the running gcd of a prefix. Once a small number enters the prefix, the gcd can only stay the same or decrease, and once it drops, it can never go back up. This makes the ordering crucial: we want large gcd values to persist for as long as possible.

The constraint n up to 100000 forces any solution to avoid checking permutations. Even O(n^2) constructions are already borderline, but anything involving pairwise gcd recomputation across all transitions would be too slow if done naively.

A few failure patterns appear quickly.

If all numbers are equal, every permutation gives the same answer because every prefix gcd stays constant. A naive greedy that tries to reorder anyway might still work but gives no benefit.

If the array contains a single 1, then once 1 appears in the prefix, all subsequent gcd values become 1. The optimal strategy clearly delays introducing 1 until the end.

If numbers share a large common divisor but a few small numbers exist, placing small numbers early collapses the gcd too soon, destroying future contributions. A naive greedy that sorts descending may still fail in cases where divisibility structure matters more than magnitude.

Approaches

A brute-force solution would try all permutations, compute prefix gcds for each, and track the maximum sum. This is factorial in n, and even generating permutations is already infeasible beyond n around 10.

A slightly less naive idea is to think greedily: at each step, pick the next element that keeps the prefix gcd as large as possible. But this local rule fails because sometimes sacrificing gcd early yields a better long-term sequence of gcd values. The decision is not purely local.

The key observation is that the prefix gcd evolves in a very structured way. Suppose at some point the current gcd is g. If we append a number x, the new gcd becomes gcd(g, x), which must be a divisor of g. So the gcd value can only move downward along the divisor lattice.

This suggests flipping the perspective: instead of thinking about permutations, we think about how many times each possible gcd value can be “maintained” across prefixes. Each time we place an element, it contributes to some divisor state transitions. We want to arrange elements so that large gcd states persist as long as possible.

Now fix a value g. We ask: how many elements in the array are divisible by g? If we are currently at gcd g, only elements divisible by g keep us at g; everything else drops the gcd below g. Therefore, if we want to maintain gcd g for k consecutive prefixes, we need at least k elements divisible by g that are “compatible” with staying at g.

This naturally leads to counting frequencies over divisors and then computing contributions from large gcd values downward. The standard technique is to compute, for every value g, how many array elements are divisible by g, and then determine how many times we can “activate” gcd value g in the optimal ordering.

The DP intuition is to build the answer by considering gcd values from large to small. For each g, we try to assign as many positions as possible where the prefix gcd is exactly g, but we must subtract contributions already claimed by multiples of g.

This is efficiently handled using divisor counting and a reverse inclusion principle over multiples.

The brute force fails because it recomputes gcd per prefix, while the optimal solution aggregates contributions by divisor classes.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n!)	O(n)	Too slow
Divisor counting + inclusion	O(A log A)	O(A)	Accepted

Algorithm Walkthrough

Count frequency of every value in the array. This lets us know how many copies of each number can contribute to gcd states.
For every integer g, compute how many array elements are divisible by g. This is done by summing frequencies of multiples of g. The reason this works is that any element divisible by g can potentially maintain a prefix gcd at least g.
Process gcd values from large to small. Larger gcd values are more valuable because they contribute larger numbers to the prefix sum, so we allocate contributions to them first.
For a fixed g, determine how many positions can have prefix gcd exactly g. This depends on how many multiples of g exist, minus the amount already assigned to multiples of g that have been processed earlier. The subtraction is necessary because those positions have already been “consumed” by stronger gcd states.
Add g multiplied by the number of positions assigned to gcd g into the final answer.
Maintain a running counter of already used positions so that smaller gcd values do not overcount elements already assigned to higher gcd states.

Why it works

The construction implicitly assigns each position in the final permutation a “responsible gcd value”, which is the highest gcd value that can be maintained when placing that element in the sequence. Because gcd can only decrease when introducing elements, each position contributes exactly one gcd value in the prefix sum, and assigning it to the largest possible valid gcd maximizes the total sum. Processing from large to small ensures that every element is claimed by the largest divisor state it can sustain, producing a globally optimal assignment.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    maxv = max(a)

    freq = [0] * (maxv + 1)
    for x in a:
        freq[x] += 1

    # count multiples
    cnt = [0] * (maxv + 1)
    for g in range(1, maxv + 1):
        for mult in range(g, maxv + 1, g):
            cnt[g] += freq[mult]

    used = [0] * (maxv + 1)
    ans = 0

    for g in range(maxv, 0, -1):
        # how many elements divisible by g not yet used by multiples
        cur = cnt[g]
        for mult in range(2 * g, maxv + 1, g):
            cur -= used[mult]

        if cur > 0:
            used[g] = cur
            ans += cur * g

    print(ans)

if __name__ == "__main__":
    solve()

The frequency array stores how many times each value appears. This is necessary because values can repeat heavily up to 10^5 elements.

The cnt[g] computation aggregates all numbers divisible by g using a standard sieve over multiples. This is the critical step that translates gcd structure into arithmetic divisibility.

The reverse loop ensures we assign contributions starting from the largest gcd values. The subtraction using already-used multiples enforces that a number cannot simultaneously contribute to multiple gcd layers.

Worked Examples

Example 1

Input:

6
2 3 1 2 6 2

We compute frequencies: 1 appears once, 2 appears three times, 3 once, 6 once.

We then compute how many numbers are divisible by each g.

g	cnt[g]	assigned
6	1	1
3	2	2
2	4	4
1	6	6

Processing from large to small, we first assign gcd 6 once, contributing 6. Then gcd 3 contributes 2 times, adding 6. Then gcd 2 contributes 4 times, adding 8. The final gcd 1 layer does not add extra contribution because all positions are already accounted for in the optimal decomposition. Summing gives 14.

This trace shows how higher gcd states are preserved first, and smaller states fill remaining structure.

Example 2

Input:

5
1 1 1 1 1

g	cnt[g]	assigned
1	5	5

All prefix gcds remain 1 regardless of ordering, so the total is 5.

This demonstrates that when all numbers are identical, the structure collapses to a single gcd layer.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(A log A)	Each g iterates over its multiples in a sieve-like pattern
Space	O(A)	Frequency and auxiliary arrays over value range

The maximum value of 5 × 10^6 makes a divisor-sieve approach acceptable in C++ and borderline in Python, but still feasible with tight loops and avoiding unnecessary overhead.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    out = io.StringIO()
    with redirect_stdout(out):
        solve()
    return out.getvalue().strip()

# sample
assert run("6\n2 3 1 2 6 2\n") == "14"

# all equal
assert run("4\n5 5 5 5\n") == "20"

# single element
assert run("1\n10\n") == "10"

# includes 1
assert run("3\n10 1 10\n") == "12"

# primes only
assert run("4\n2 3 5 7\n") == "17"

Test input	Expected output	What it validates
all equal	linear scaling	stability of identical values
single element	value itself	base case correctness
includes 1	delayed collapse of gcd	effect of absorbing element
primes only	minimal gcd structure	behavior with no shared divisors

Edge Cases

When all values are identical, every prefix has the same gcd and the algorithm assigns all elements to gcd 1 without distortion. The divisor counting does not introduce spurious structure because every number contributes equally to all divisor buckets.

When the array contains 1, the cnt[1] bucket includes everything, but higher gcd buckets remain unaffected. During reverse processing, larger gcd layers are assigned first, and 1 only collects what remains unassigned, which matches the fact that once 1 appears in a prefix, gcd cannot increase again.

When all numbers are pairwise coprime, only gcd 1 has meaningful multiplicity. The algorithm correctly reduces the entire structure to a single layer at g = 1, producing a linear sum equal to n.