P5036 Randomly Generated Tree

An easy problem adapted by @Gejun.

Rainheavy drew $N$ points on paper (numbered from $1$ to $N$). The color of each point is described by an integer. Rainheavy decides to randomly generate a tree using these $N$ points. The rules are as follows. For points $2$ to $N$, each point randomly chooses one point to connect to. The point that node $i$ $(2 \le i \le N)$ connects to is randomly selected from: the divisors of $i$, and the multiples of $i$ that do not exceed $N$. (For example, when $N=30$, node $10$ can connect to node $1$, $2$, $5$, $20$, or $30$.) The generated tree cannot have multiple edges. (Otherwise it would not be a tree.) After the tree is generated, Rainheavy can compute how many connected components it has. A connected component is a set of points that must satisfy the following two conditions. 1. For any two points chosen from the set: the two points have the same color, and there exists a path consisting of tree edges between them such that all points on the path have the same color as these two points. 2. For any point inside the set and any point outside the set: the two points are either of different colors, or there does not exist a path consisting of tree edges between them such that all points on the path have the same color as these two points. Rainheavy wants to find, when the number of connected components in the generated tree is maximized, which edges should be connected. However, Rainheavy is too strong and does not bother with such a boring problem. ~~More importantly, he is going to AK IOI~~, so he throws the problem to you. Note: the order of edges. 1. First, prioritize maximizing the number of connected components (i.e., prioritize edges that contribute to forming connected components). 2. If condition 1 is tied, prioritize the edge with the smaller sum of the two endpoint indices. (For example, under condition 1, the edge connecting node $3$ and node $5$ has higher priority than the edge connecting node $4$ and node $5$.) 3. If condition 2 is also tied, prioritize the edge whose smaller endpoint index is smaller. (For example, under condition 2, the edge connecting node $2$ and node $6$ has higher priority than the edge connecting node $3$ and node $5$.)

The first line contains an integer $N$, representing the number of nodes. The second line contains $N$ integers. The $i$-th integer $c_i$ represents the color of node $i$.

Output a total of $N-1$ lines. Each line contains two integers $x,y$, indicating that an edge should connect node $x$ and node $y$. (It is required that $x

Explanation for the sample: Because nodes $2$ and $4$ will contribute to forming connected components (connecting node $3$ is useless), and since $1+2 \lt 1+4$, $(1,2)$ should be output before $(1,4)$, and finally output $(1,3)$. Constraints: For $30\%$ of the testdata, $2 \le N \le 10$. For $60\%$ of the testdata, $2 \le N \le 5000$. For $80\%$ of the testdata, $2 \le N \le 2 \times 10^5$. For $100\%$ of the testdata, $2 \le N \le 5 \times 10^5$, $1 \le c_i \le 10^9$. (Anyway, bigger is useless.) Translated by ChatGPT 5