Editorial for DMOPC '19 Contest 7 P4 - Bob and Continued Fractions


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

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.


Comments

There are no comments at the moment.