ezraft and Array

Let the sum of the array be

$S=a_1+a_2+\cdots+a_n.$

We need every $a_i$ to be a divisor of $S$. Trying to guess $n$ divisors of some giant number is unnecessary pain. The much cleaner move is to grow a valid array one element at a time.

The extension trick

Assume we already have a valid array of distinct positive integers whose sum is $S$. Append one new element equal to $S$.

The new sum is

$S+S=2S.$

Now check every element:

• Every old element divides $S$, so it also divides $2S$.
• The new element is $S$, which clearly divides $2S$.
• Since the old array contains at least two positive elements, every old element is strictly smaller than their total $S$. Therefore, the appended value is new and distinct.

So one valid array immediately gives a valid array with one more element. The construction is almost offensively simple once you see it.

Finding a seed

For three elements, use

$[1,2,3].$

Its sum is $6$, and $1$, $2$, and $3$ all divide $6$.

Repeatedly appending the current sum gives

$[1,2,3,6,12,24,48,\ldots].$

For example:

• $[1,2,3]$ has sum $6$.
• Append $6$; now the sum is $12$.
• Append $12$; now the sum is $24$.
• Append $24$; now the sum is $48$.

The invariant remains true after every append.

The small cases

$n=1$

Output $[1]$. Its sum is $1$, which is divisible by its only element.

$n=2$

A solution is impossible. Suppose the two distinct positive integers are $x<y$. Because their sum must be divisible by $y$,

$y\mid(x+y).$

We also have $y\mid y$, so subtracting gives $y\mid x$. But $0<x<y$, and no positive number smaller than $y$ can be divisible by $y$. Contradiction.

Thus, $n=2$ is the only impossible case.

$n\ge3$

Start with $[1,2,3]$ and append the current sum until the array has $n$ elements.

Correctness proof

We prove that the algorithm produces a valid answer whenever $n\ne2$.

For $n=1$, the algorithm outputs $[1]$, whose sum is divisible by its only element.

Now consider $n\ge3$. Initially, the array is $[1,2,3]$ with sum $6$, so all elements are distinct positive integers and each divides the sum.

Assume before some iteration that the current array is valid and has sum $S$. The algorithm appends $S`, making the new sum$2S$.

Every previous element divides $S$, hence divides $2S$. The appended element $S$ also divides $2S$. Furthermore, $S$ is greater than every previous element because it is their sum and there are multiple positive elements. Therefore, the appended element is distinct from all previous elements.

The array remains valid after the iteration. By induction, the final array is valid and has exactly $n$ elements.

Finally, the impossibility argument above proves that no valid array exists for $n=2$.

Value bound

Starting from sum $6$, every extension doubles the sum. For position $i\ge4$, the value appended is

$a_i=6\cdot2^{i-4}.$

At the maximum $n=50$, the largest output value is

$6\cdot2^{46}=422212465065984<10^{17}.$

It also fits comfortably inside long long.

Complexity

For each test case, the algorithm uses $O(n)$ time and $O(n)$ memory.