Linear Recurrence for very large n
- by Android Decoded
I was trying to solve this problem on SPOJ (http://www.spoj.pl/problems/REC/)
F(n) = a*F(n-1) + b where we have to find F(n) Mod (m)
where
0 <= a, b, n <= 10^100
1 <= M <= 100000
I am trying to solve it with BigInteger in JAVA but if I run a loop from 0 to n its getting TLE. How could I solve this problem? Can anyone give some hint? Don't post the solution. I want hint on how to solve it efficiently.