The key observation for this problem is that given the fraction ~\frac a b~ in lowest terms, ~k + \frac{1}{\frac a b}~ will also be in lowest terms.

The proof is as follows. Simplifying the expression yields ~k + \frac b a = \frac{ka + b}{a}~. Let us consider ~\gcd(ka + b, a)~. By the Euclidean algorithm, we know this equals ~\gcd(b, a)~, and as ~\frac a b~ is in lowest terms, ~\gcd(ka + b, a) = \gcd(b, a) = 1~. QED

Thus if we represent the fraction ~\frac a b~ as the matrix ~\begin{bmatrix} a \\ b\end{bmatrix}~, we can express ~k + \frac{1}{\frac a b}~ as the matrix ~\begin{bmatrix} k & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} a \\ b\end{bmatrix}~.

For 10% of points, we can answer each query by multiplying together the corresponding matrices.

Time Complexity: ~\mathcal O(NQ)~

For the remaining 90% of points, we can use a range tree and the associative property of matrix multiplication to obtain a solution in ~\mathcal O(Q \log N)~.

Alternatively, we can use a technique similar to the idea of prefix sum arrays. Note that ~\begin{bmatrix} k & 1 \\ 1 & 0 \end{bmatrix}^{-1} = \begin{bmatrix} 0 & 1 \\ 1 & -k \end{bmatrix}~. We can precompute ~\prod\limits_{i = 1}^k \begin{bmatrix} a_i & 1 \\ 1 & 0 \end{bmatrix}~ and ~\prod\limits_{i=1}^k \begin{bmatrix} 0 & 1 \\ 1 & -a_i \end{bmatrix}~ for ~k = 1, 2, \dots, N~ in ~\mathcal O(N)~, thus the product ~\prod\limits_{i=l}^{r-1} \begin{bmatrix} a_i & 1 \\ 1 & 0 \end{bmatrix}~ can be found in ~\mathcal O(1)~.

Time Complexity: ~\mathcal O(N + Q)~

A final solution is as follows. We claim that for any continued fraction $$\displaystyle a_1 + \frac{1}{a_2 + \frac{1}{\ddots + \frac{1}{a_k + \frac{1}{x}}}}$$ there exists ~a,b,c,d~ such that $$\displaystyle a_1 + \frac{1}{a_2 + \frac{1}{\ddots + \frac{1}{a_k + \frac{1}{x}}}} = \frac{ax + b}{cx + d}.$$

This is equivalent to the matrix solution, and the proof of correctness is left as an exercise for the reader.