Editorial for DMOPC '19 Contest 7 P4 - Bob and Continued Fractions
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
The key observation for this problem is that given the fraction in lowest terms, will also be in lowest terms.
The proof is as follows. Simplifying the expression yields . Let us consider . By the Euclidean algorithm, we know this equals , and as is in lowest terms, . QED
Thus if we represent the fraction as the matrix , we can express as the matrix .
For 10% of points, we can answer each query by multiplying together the corresponding matrices.
Time Complexity:
For the remaining 90% of points, we can use a range tree and the associative property of matrix multiplication to obtain a solution in .
Alternatively, we can use a technique similar to the idea of prefix sum arrays. Note that . We can precompute and for in , thus the product can be found in .
Time Complexity:
A final solution is as follows. We claim that for any continued fraction there exists such that
This is equivalent to the matrix solution, and the proof of correctness is left as an exercise for the reader.
Comments