SPOJ Problem Set (classical)
10966. Aritho-geometric Series (AGS)
Problem code: AGS
|
Arithmatic and geometric Progressions are 2 of the well known progressions in maths.
Arithmatic progression(AP) is a set in which the difference between 2 numbers in constant. for eg, 1,3,5,7,9 .... In this series the difference between 2 numbers is 2.
Geometric progression(GP) is a set in which the ratio of 2 consecutive numbers is same. for eg, 1,2,4,8,16.... In this the ratio of the numbers is 2.
.....
What if there is a series in which we multiply a(n) by 'r' to get a(n+1) and then add 'd' to a(n+1) to get a(n+2)...
For eg .. lets say d=1 and r=2 and a(1) = 1..
series would be 1,2,4,5,10,11,22,23,46,47,94,95,190 ......
We add d to a(1) and then multiply a(2) with r and so on ....
Your task is, given 'a' , 'd' & 'r' to find the a(n) term .
sicne the numbers can be very large , you are required to print the numbers modulo 'mod' - mod will be supplied int the test case.
Input
first line of input will have number 't' indicating the number of test cases.
each of the test cases will have 2 lines
firts line will have 3 numbers 'a' ,'d' and 'r'
2nd line will have 2 numbers 'n' & 'mod'
a- first term of the AGS
d-the difference element
r - the ratio element
n- nth term required to be found
mod- need to print the result modulo mod
Output
For each test case print "a(n)%mod" in a separate line.
Example
Input:
2
1 1 2
13 7
2 2 2
10 8
Output:
1
6
Description - for the first test case the series is 1,2,4,5,10,11,22,23,46,47,94,95,190..
13th term is 190 and 190%7 = 1
Note - the value of a , d , r , n & mod will be less than 10^8 and more than 0.
for every series 2nd term will be a+d and third term will be (a+d)*r .. and so on ..
RSS