P6756 [BalticOI 2013] Brunhilda's Birthday

There is an integer $n$ and a prime list $p$ of length $m$. You may perform any number of operations. In each operation, you choose a prime $p_i$, which changes $n$ to $n \to \lfloor \frac{n}{p_i} \rfloor \times p_i$. Your goal is to find the minimum number of operations needed to make $n$ become $0$. If it is impossible to make it $0$, output `oo`. To make it harder, you need to answer $Q$ queries of $n$.

The first line contains two integers $m, Q$. The next line contains $m$ integers $p$. The next $Q$ lines each contain one integer $n$, representing the value of $n$ given in each query.

For each query, output the minimum number of operations needed to make $n$ become $0$. If it is impossible, output `oo`.

#### Constraints and Limits - For the testdata worth $20$ points, it is guaranteed that $m, n, Q \le 10^4$. - For another $20$ points of testdata, it is guaranteed that $Q = 1$. - For $100\%$ of the testdata, it is guaranteed that $1 \le m, Q \le 10^5$, $2 \le p_i \le 10^7$ and $p_i$ is prime, and $1 \le n \le 10^7$. #### Notes This problem is translated from [Baltic Olympiad in Informatics 2013](https://boi.cses.fi/tasks.php) [Day 2](https://boi.cses.fi/files/boi2013_day2.pdf) T1 Brunhilda’s Birthday. Because the translator could not find a suitable setting, this problem has a full score of $110$ points. Translated by ChatGPT 5