FRSKH - Fibonacci recursive sequences (hard)
Leo searched for a new fib-like problem, and ...
it's not a fib-like problem that he found !!! Here it is.
Let FIB the Fibonacci function :
FIB(0)=0 ; FIB(1)=1
for N>=2 FIB(N) = FIB(N-1) + FIB(N-2)
Example : we have FIB(6)=8, and FIB(8)=21.
Let F(K, N) a new function:
F(0, N) = N for all integers N.
F(K, N) = F(K-1, FIB(N) ) for K>0 and all integers N.
Example : F(2, 6) = F(1, FIB(6) ) = F(0, FIB( FIB(6) ) ) = FIB( FIB(6) ) = FIB(8) = 21
The input begins with the number T of test cases in a single line.
In each of the next T lines there are three integers: K, N, M.
For each test case, print F(K, N),
as the answer could not fit in a 64bit container,
give your answer modulo M.
Input: 3 4 5 1000 3 4 1000 2 6 1000 Output: 5 1 21
1 <= T <= 10^3 0 <= K <= 10^18 0 <= N <= 10^18 2 <= M <= 10^18
K, N, M are uniform randomly chosen.
You would perhaps have a look, before, at the medium edition with easier constraints.
Edit(12/I/2015) My old Python code now ends in 2.19s using PY3.4 and cube cluster.
Edit(11/2/2017) Compiler updates ; my old Python3.5 code ends in 0.98s. New TL.
This is the second hardest problem for me.
@Francky can you please tell me if my approach is correct or not?
Great problem, thanks Francky!
Yay, finally accepted ;). Thank you for such an awesome problem (but hard as hell simultaneously ;)).