Product Queries

The repeated-use part is the whole problem. Once a value $x$ appears in the array, it can be used any number of times, so duplicates do not matter at all. We only care about the set

$S=\{a_i\}.$

For every product $v$, let $dp[v]$ be the minimum number of selected elements needed to obtain product $v$. Internally, use

$dp[1]=0$

as the empty product. That does not mean the answer for $1$ is $0$; the statement requires selecting at least one element. This is just a clean DP starting point.

For any available value $x>1$, if product $v$ is reachable, then product $v\cdot x$ is reachable with one more selected element:

$dp[v\cdot x] = \min(dp[v\cdot x], dp[v]+1).$

We only apply this when $v\cdot x\le n$, because answers are needed only for $1$ through $n$.

A nice way to view this is as a graph. The vertices are numbers $1,2,\dots,n$. For every available multiplier $x>1$, add an edge

$v \to v\cdot x$

with cost $1$. We need shortest distances from $1$.

Normally “shortest paths” might make you reach for BFS, but here every edge strictly increases the number, since $x>1$. So the graph is a DAG, and the natural order

$1,2,3,\dots,n$

is already topological. Process $v$ from small to large. When $dp[v]$ is known, relax all transitions using available multipliers.

To keep it efficient, store all distinct available values greater than $1$. For each reachable $v$, stop the multiplier loop once $x>n/v$. Since the values are sorted, this is easy.

The total number of useful relaxations is bounded by

$\sum_{x\in S,\ x>1} \left\lfloor \frac{n}{x}\right\rfloor \le n\sum_{x=2}^{n}\frac1x = O(n\log n).$

Now handle the annoying little edge case: product $1$. The only way to get product $1$ while selecting at least one element is to select value $1$. Multipliers greater than $1$ can never help. Therefore:

• answer for $1$ is $1$ if $1\in S$;
• otherwise answer for $1$ is $-1$.

For every $i>1$, if $dp[i]$ stayed infinite, output $-1$; otherwise output $dp[i]$.

Correctness follows from the transition matching exactly one extra selected element. Any valid product representation

$i = x_1x_2\cdots x_k$

with each $x_j\in S$ and $x_j>1$ corresponds to a path

$1\to x_1\to x_1x_2\to\cdots\to i$

of length $k$, so the DP can find it. Conversely, every DP transition multiplies by an actually available array value, so every reached state is a real selectable product. Since states are processed in increasing order and every transition goes to a larger state, all ways to reach $v$ have already been considered before $v$ is used to update larger products.

Complexity per test case is

$O\left(n + \sum_{x\in S,x>1}\left\lfloor\frac nx\right\rfloor\right)=O(n\log n),$

with $O(n)$ memory.