Let $d(n)$ denote the number of calls Wotan needs to end the game when $n$ children are left and let $M=\{k_1,\dots ,k_m\}$ be the set of primes Wotan can choose from.

Dynamic Programming Solution

For $20$ points it is enough to evaluate the obvious formula

$${\displaystyle d(n)=1+\underset{k\in M}{min}d(n-(nmodk))}$$

using dynamic programming. Then all queries can be answered by simple lookup. To handle the case $d(n)=\mathrm{\infty }$ suffices to check whether

$${\displaystyle n\ge \text{lcm}(k_1,\dots ,k_m)=\prod _{k\in M}k}$$

(since if $n$ is not divisible by $k$ after calling $k$ less children will be over, but if $n$ is at least the product $p$ of all numbers Wotan can call, after any call at least $p$ children will remain) or to simply set $d(n)=1$ for $n\ne 0$ before evaluating the above formula. Runtime is $\mathrm{\Theta }(mn+Q)$ in both cases.

Greedy Approach

Let us denote the predecessor, i.e. the number of children that are left after Wotan made a perfect call, of $n$ as $\pi (n$). If there are multiple solutions, let $\pi (n)$ be the minimum of these numbers. The main point of the solution is the following

Proposition 1. Wotan can call the numbers greedily, i.e. $\pi (n)=\underset{k\in M}{min}(n-(nmodk))$. This fact is—once stated—quite obvious, but it can be established rigorously using the following

Lemma 2. $\pi$ and $d$ are both monotonically increasing in $n$.

Proof. We show this for any interval $[0\dots N]$ by induction on $N$. Without loss of generality let us assume that $d(N)<1$. The case $N=0$ is trivial. Otherwise we have $\pi (N)\le N-1$ as stated above and thus $\pi (N)=\underset{k\in M}{min}(N-(Nmodk))$. Since $(N-1)modk\ge (Nmodk)-1$ for any $N$, $k$ we have $\pi (N)\ge \pi (N-1)$. Thus

$${\displaystyle d(N)=d(\pi (N))+1\ge d(\pi (N-1))+1\ge d(N-1)}$$

because of the monotonicity of $d$ in $[0\dots \pi (N)]\subseteq [0\dots N-1]$.

To show that this suffices for subtask $2$ we need to establish an upper bound for $d(n)$. For simplicity let $k_{max}$ denote $maxM$.

Lemma 3. Let $n=n^{\prime }{k}_{max}$ and $d(n)<1$. Then $d(n)\le 2n^{\prime }$.

Proof. We use induction on $n^{\prime }$. Again there is nothing to show for $n^{\prime }=0$. For $n^{\prime }\ge 1$ we have $\pi (n)<n$ by assumption and thus

$${\displaystyle \pi (\pi (n))\le \pi (n-1)\le (n-1)-((n-1)mod{k}_{max})=(n-1)-(k_{max}-1)=n-k_{max}=(n^{\prime }-1)k_{max}}$$

by monotonicity of $\pi$. Using the monotonicity of $d$ we get thus $d(n)=d(\pi (\pi (n)))+2\le d((n^{\prime }-1)k_{max})+2=2(n^{\prime }-1)+2=2n^{\prime }$.

Once again using monotonicity we get

Corollary 4. If $d(n)<1$, then $d(n)\le \lceil \frac{2n}{k_{max}}\rceil$. Especially we have $d(n)=\mathcal{O}\left(\frac{n}{m}\right)$.

Using the prime number theorem stating that the $n^{\text{th}}$ prime is asymptotically as big as $n\ln n$ one can decrease this bound further to $\mathcal{O}\left(\frac{n}{m\log m}\right)$, however, this is not required directly for the solution.

Since we can calculate $\pi (n)$ primitively in $\mathcal{O}(m)$ we can answer one query in $\mathcal{O}(m+n)$ time. This suffices for subtasks $1$ and $2$.

DP Over Inverse Function

Let $d^{(-1)}$ denote the inverse function of $d$, i.e.

$${\displaystyle d^{(-1)}(k)=max\{n:d(n)\le k\}.}$$

Since $\pi (k+k_{max})>k$ and thus $d(k+k_{max})>d(k)$, we have

$${\displaystyle d^{(-1)}(k+1)>d^{(-1)}(k)+k_{max}}$$

Thus having calculated $d^{(-1)}(x)$ for $x\in [1\dots k]$ one can calculate $d^{(-1)}(k+1)$ using binary search in the interval $[d^{(-1)}(k),d^{(-1)}(k)+k_{max}]$. It further suffices to check for given $x$ in this interval whether $\pi (x)>d^{(-1)}(k)$ (instead of really calculating $d(x)$, which would be too slow). So one can calculate this function for every needed value of $k$ in time $\mathcal{O}(n+m)$ (here the additional log-factor mentioned before comes in handy).

With this function one can answer any query in logarithmic time using binary search or simply fill an array $d[1\dots n]$ of all values in time $\mathcal{O}(n)$ and then answer queries in $\mathcal{O}(1)$. Both suffices to get full score.

Model Solution: Fast Evaluation of the Predecessor Function

Instead of minimizing $\pi (n)$ we can simply maximize the term we subtract (since $n$ is fixed), let's call it $\mu (n,k)=nmodk$. If we plot some of those functions for variable $n$ and some $k\in M$ the image consists of a set of straight lines of slope $1$ and "breaks".

Thus for ${\mu }^{\ast }(n):=\underset{k\in M}{max}\mu (n,k)$ we get the same simple characteristic. If we plot all those functions — both $\mu$ and ${\mu }^{\ast }$ — and scan through this image from right to left the optimal $k$ can only change when a break occurs. Thus if we evaluate ${\mu }^{\ast }$ at all those breaks of all the $\mu$-functions we can simply fill in the rest of them by subtracting one from the next one at the right.

For any breakpoint $n$, we have that ${\mu }^{\ast }(n-1)$ is $k-1$ for some $k\in M$. Thus to initialize our array $M[1\dots n]$ of values of ${\mu }^{\ast }$ it suffices to set $M[ak-1]=k-1$ for any $a$ and increasing $k\in M$. This needs

$${\displaystyle \sum _{k\in m}\frac{n}{k}=n\sum _{k\in m}\frac{1}{k}\le n\sum _{i=1}^m\frac{1}{k}=n{H}_m=\mathcal{O}(n\log m)}$$

steps (messing with analytic number theory one can reduce this bound further to $\mathcal{O}(n\log \log m)$ but with really good constant factor.

Afterwards one can calculate $\pi (n)$ on the fly in constant time and thus use the simple DP approach from the beginning to get full score.

An implementation using a priority queue to evaluate ${\mu }^{\ast }$ using the same ideas above is expected to get something around full score, too, depending on the data structure used.