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 + \min_{k \in M} d(n-(n \bmod k))$$

using dynamic programming. Then all queries can be answered by simple lookup. To handle the case ~d(n) = \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 ~\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) = \min_{k \in M}(n-(n \bmod k))~. 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) = \min_{k \in M} (N-(N \bmod k))~. Since ~(N-1) \bmod k \ge (N \bmod k)-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 ~\max M~.

Lemma 3. Let ~n = n' k_{\max}~ and ~d(n) < 1~. Then ~d(n) \le 2n'~.

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

$$\displaystyle \pi(\pi(n)) \le \pi(n-1) \le (n-1)-((n-1) \bmod k_{\max}) = (n-1)-(k_{\max}-1) = n-k_{\max} = (n'-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'-1)k_{\max})+2 = 2(n'-1)+2 = 2n'~.

Once again using monotonicity we get

Corollary 4. If ~d(n) < 1~, then ~d(n) \le \left\lceil \frac{2n}{k_{\max}} \right\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) = n \bmod k~. 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^*(n) := \max_{k \in M} \mu(n, k)~ we get the same simple characteristic. If we plot all those functions — both ~\mu~ and ~\mu^*~ — and scan through this image from right to left the optimal ~k~ can only change when a break occurs. Thus if we evaluate ~\mu^*~ 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^*(n-1)~ is ~k-1~ for some ~k \in M~. Thus to initialize our array ~M[1 \dots n]~ of values of ~\mu^*~ 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^*~ using the same ideas above is expected to get something around full score, too, depending on the data structure used.