Sphere Online Judge

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.


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.5s
Source limit:10000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)

hide comments
2014-01-22 13:28:32 Piyush Raman Srivastava
wrong assumptions by problem solvers and an awesome mathematics!! Thanx a lot @Devil D :)
2013-12-30 12:36:57 shiva_hellgeek
Got 15 WAs in summer vacations.
Now AC in 1 go in Winters ;)
Really enjoyed solving this one.
2013-08-05 08:20:46 darryl
It seems that the testcase lacks condition where a+d is bigger than the mod.
2013-07-18 09:47:52 Hasil Sharma

Last edit: 2013-11-11 18:42:32
2013-07-04 12:57:56 pm
getting wa in python at running(4),
nd tle in C(same algo)at running(5) ... pls help ?? if dere any tricky case.....

Last edit: 2013-07-04 13:12:04
2013-06-19 15:20:42 Shubham Gupta
Getting WA in the 5th case, can anyone suggest something where I am going wrong? pls pls
2013-06-19 14:41:51 Man Mohan Mishra
awesome problem.....
maths involved !!
got AC in 2nd attempt :)
2013-06-08 08:46:45 Ankur
Finally Finally that green light !!! :) :)
Learnt a new thing about % ..
Great Problem.. Thanks @Devil D

Last edit: 2013-06-08 11:49:26
2013-06-07 13:31:06 Aditya Bahuguna
this one was not that easy.... :) Greatest relief!!! AC'

Last edit: 2013-06-07 13:37:51
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.