P7854 "EZEC-9" GCD Tree

Let $\gcd(x,y)$ denote the greatest common divisor of $x$ and $y$, and let $\operatorname{lca}(x,y)$ denote the lowest common ancestor of node $x$ and node $y$.

You are given $n$ nodes, numbered $1,2,\ldots,n$, with weights $a_1,a_2,\ldots,a_n$. Please use these $n$ nodes to construct a tree such that for all $1 \le i < j \le n$, $\gcd(a_i, a_j) = a_{\operatorname{lca}(i, j)}$. If there is no solution, report it. Otherwise, output the shape of the tree.

The first line contains an integer $n$. The second line contains $n$ integers $a_1, a_2, \ldots , a_n$.

If there is no solution, output `-1`. Otherwise, output one line with $n$ integers. The $i$-th number denotes the parent index of node $i$. In particular, if node $i$ is the root, output `0`. If there are multiple solutions, output any one of them.

**【Constraints and Notes】** **This problem uses bundled testdata.** - Subtask 1 (5 points): $n = 2$. - Subtask 2 (5 points): all $a_i$ are equal. - Subtask 3 (5 points): $n \le 5$. - Subtask 4 (10 points): a solution is guaranteed to exist. - Subtask 5 (15 points): $n \le 100$. - Subtask 6 (15 points): $n \le 10^3$. - Subtask 7 (15 points): $n \le 3 \times 10^3$. - Subtask 8 (30 points): no special restrictions. For $100\%$ of the testdata, $2 \le n \le 10^5$ and $1 \le a_i \le 10^6$. Translated by ChatGPT 5