RECEQU - Recurrence Equation Finder
Many problems have solutions involving linear recurrence equations of the form f(n) = a · f(n-1) + b · f(n-2) (n ≥ 2). Usually the coefficients a and b are between 0 and 10, so it would be useful to have a program which checks if some given values can be produced by such a recurrence equation. Since the growth of the values f(n) can be exponential, we will consider the values modulo some integer constant k.
More specifically you will be given f(0), f(1), k and some value pairs (i , xi), where xi is the remainder of the division of f(i) by k.
You have to determine coefficients a and b for the recurrence equation f such that for each given value pair (i, xi) the equation xi = f(i) mod k holds.
Hints
You can write the recurrence equation as follows:
Let
Then, . These equations also apply if everything is calculated modulo k. To speed up the calculation of An, the identity An = (An div 2)2 · An mod 2 may be used. Also, (a · b) mod c = ((a mod c) · (b mod c)) mod c.
Input
The first line of the input contains a number T ≤ 20 which indicates the number of test cases to follow.
Each test case consists of 3 lines. The first line of each test case contains the three integers f(0), f(1) and k, where 2 ≤ k ≤ 10000 and 0 ≤ f(0),f(1) < k. The second line of each test case contains a number m ≤ 10 indicating the number of value pairs in the next line. The third line of each test case contains m value pairs (i,xi), where 2 ≤ i ≤ 1000000000 and 0 ≤ xi < k.
Output
For each test case print one line containing the values a and b separated by a space character, where 0 ≤ a,b ≤ 10. You may assume that there is always a unique solution.
Example
Input: 2 1 1 1000 3 2 2 3 3 16 597 0 1 10000 4 11 1024 3 4 1000000000 4688 5 16 Output: 1 1 2 0
Added by: | Adrian Kuegel |
Date: | 2007-01-18 |
Time limit: | 1.436s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |