P14444 [ICPC 2025 Xi'an Practice] Great Indices

You are given a sequence $a_1, a_2, \cdots, a_n$. For each $1 \leq i \leq n$, index $i$ is called $\textit{great}$ if and only if the following holds: - There is at most one index $1 \leq j \leq n$ such that $a_j$ is not a divisor of $a_i$. Your task is to find all $\textit{great}$ indices in the sequence. Recall that an integer $d$ is a divisor of an integer $n$ if and only if there exists an integer $k$ such that $n = d \times k$.

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^5$), the number of test cases. For each test case: - The first line contains a single integer $n$ ($1 \leq n \leq 3 \times 10^5$), representing the length of sequence $a$. - The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \leq a_i \leq 10^9$), representing the given sequence. It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \times 10^5$.

For each test case, output two lines: - The first line contains a single integer $m$, representing the number of $\textit{great}$ indices. - The second line contains $m$ integers $p_1, p_2, \cdots, p_m$ ($p_1 < p_2 < \cdots < p_m$), representing the $\textit{great}$ indices $\textbf{in increasing order}$.

In the first test case: - When $i = 1$, the indices $j$ where $a_j$ is not a divisor of $a_i$ are $2$, $3$, and $4$. Since $3 > 1$, index $1$ is not a $\textit{great}$ index. - When $i = 2$, there are two indices, $j = 3$ and $j = 4$, for which $a_j$ is not a divisor of $a_i$. - When $i = 3$, there are two indices, $j = 2$ and $j = 4$, for which $a_j$ is not a divisor of $a_i$. - When $i = 4$, each of $a_j$ is a divisor of $a_i$, so that index $4$ is a $\textit{great}$ index. Therefore, the only $\textit{great}$ index is $i = 4$.