AGS - Aritho-geometric Series (AGS)

no tags 

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.


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


For each test case print "a(n)%mod" in a separate line.


1 1 2
13 7
2 2 2
10 8



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 ..

Added by:Devil D
Time limit:0.121s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)

hide comments
Babu: 2015-07-30 18:01:26

where are the fucking constraints??? -_-

Bhuvnesh Jain: 2015-07-19 09:40:56

What a brilliant question! Finally ac after long struggle. New method for sum of GP.... Can't believe it was AC in 0.00 sec.... phew

ABHISHEK004: 2015-02-26 22:57:27

tried after 2 years ...
finally accepted :)
feeling relaxed

i need you: 2014-12-29 21:09:06

very nice problem...wasted 2 days
but finally got AC.

Aditya Paliwal: 2014-12-17 23:10:11

Took just 5 mins to derive formula but 4 hours to code it! Amazing problem! Seemed like I have solved similar problems before but I had to learn something new :) Awesome!

Last edit: 2014-12-17 23:10:38
Prateek chandan: 2014-08-25 23:49:28

I have tried for all test cases but still WA
Please help
ID : 12235014

Bhavik: 2014-06-16 21:24:01

Last edit: 2014-06-24 10:25:40
Smriti Vashisth: 2014-05-22 16:03:32

getting WA despite checking all the cases
plz help Devil D

Last edit: 2014-06-08 12:18:51
Piyush Raman Srivastava: 2014-01-22 13:28:32

wrong assumptions by problem solvers and an awesome mathematics!! Thanx a lot @Devil D :)

shiva_hellgeek: 2013-12-30 12:36:57

Got 15 WAs in summer vacations.
Now AC in 1 go in Winters ;)
Really enjoyed solving this one.