DMOPC '19 Contest 7 P4 - Bob and Continued Fractions

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 128M

Problem type

A continued fraction is an expression of the form \displaystyle a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\ddots + \frac{1}{a_n}}}} where a_1, a_2, a_3, \dots, a_n are positive integers.

Bob has managed to obtain an array A of N positive integers. He now wants to compute Q continued fractions, the i-th of which uses the elements from indices l_i to r_i (inclusive) in the array, in order. For example, if A = [1, 4, 5, 2], l_i = 2, and r_i = 4, the answer would be: \displaystyle 4 + \frac{1}{5 + \frac{1}{2}} =4 + \frac{2}{11} = \frac{46}{11} Please help Bob with this task!


1 \le N, Q \le 300\,000
1 \le A_i \le 10^9
1 \le l_i \le r_i \le N

Subtask 1 [10%]

1 \le N,Q \le 1000

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input will contain two space-separated integers, N and Q.
The second line will contain N space-separated integers, A_1 through A_N.
The next Q lines will each contain two space-separated integers, l_i and r_i.

Output Specification

Q lines, each containing two space-separated integers: the numerator and denominator of the i-th continued fraction, in lowest terms. Since these numbers may be very large, you may output them mod 10^9 + 7. However, note that the fraction must be in lowest terms before modding; reducing the fraction after modding may not yield the same result!

Sample Input

4 3
1 4 5 2
2 4
1 2
3 3

Sample Output

46 11
5 4
5 1


There are no comments at the moment.