Problems
4. TheGluconProblem
The Great Glucon Problem
Deers at the Guindy National Park multiply are found to multiply according to the following law.
Let A(n) be the numbers of deers in the nth year.
Then,
A(n+1) = floor ( (A(n))^2 / (A(n-1)) + 0.5 )
(Note : NOT INTEGER DIVISION.)
You are given the number of Deers in the first and second years. Calculate the number of deers in the nth year. But since this number can become too large, print the number of deers modulo 10000007. This means, you have to print the remainder when the number of deers is divided by 10000007.
You are also given that if the number of deers is not in Geometric Progression then
A(n+1)^2 - A(n)*A(n+2) divides A(n+1)*A(n+2) - A(n)*A(n+3)
and
A(n+1)^2 - A(n)*A(n+2) divides A(n+1)*A(n+3) - A(n+2)^2
Input Format:
- Line 1 : A single integer T, the number of testcases.
- This is followed by T test cases.
- Each test cases consists of a single line with 3 integers.
- The first integer is A(1) = number of deers in year 1.
- Second integer is A(2) = number of deers in year 2.
- Third integer is n = the year for which you are to calculate the population of deers.
Output Format:
Output consists of T lines.
The ith line contains the remainder when A(n) is divided by 10000007.
Constraints:
1 <= T <= 10000
N fits in a 32-bit signed integer(int).
1 <= A(1) <= A(2) <= 100
Points:
350
Scoring:
Absolute Score = 1000000 / ( 5*S + C + 10*K + 3*O )
where,
S = Number of semicolons ;
C = Number of non-whitespace characters
K = Number of keywords
O = Number of commas ,
Allowed Header Files:
stdio.h
Sample Input:
2
1 2 4
2 7 5
Sample Output:
8
317