SPOJ.com - Problem FMODF

FMODF - Fimodacci

no tags

After solving Fib-Factorization and ModFib-Period, you would probably be interested by solving this new task:
Simply compute Fib(N) mod Fib(K), where Fib(N) denotes the Nth term of the Fibonacci sequence.
(If N<2 Fib(N)=N, else Fib(N)=Fib(N-1)+F(N-2)).

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are two integers N, K.

Output

For each test case, on a single line, print Fib(N) mod Fib(K).

Example

Input:
2
5 5
13 5

Output:
0
3

Constraints

1 < T < 10^5
1 < N < 10^18
1 < K <= 10^3

Edit(2017-02-11) : New time limit (after compiler changes).

Submit solution!

hide comments



	[Lakshman]: 2013-07-30 10:59:26 @Franky I don't understand test cases Fib(K)5=20 and fib(5)=5, why answer is 0,also fib(13)=233%20 =13 why answer is 3, Might be I m thinking wrong. --ans--> "Fib(K)5=20" ???. We have Fib(5) = 5, and Fib(13) = 233, so 5 Mod 5 gives 0 for the first case, and 233 Mod 5 gives 3 for the second one. My definition seems simple and clear, isn't it ? Good luck. (Lakshman)---> Got it. I was wrong..But TLE now. Last edit: 2013-07-30 18:37:00
	[Rampage] Blue.Mary: 2013-03-09 13:31:16 Your Python 3 code run under 0.7 sec -> Time limit should be at least 2 sec. My Pike code output 80000 answers in ~1sec. I don't think that code should get TLE. --ans--> I always thought PIKE was faster than Python, especially on that kind of task, it was false. I'm very new with PIKE and my poor translation need 1.4s, and yours 1.25 (approx). So you're absolutely in right to demand more time. It will be 2s for now, thanks for your catch. I'll rejudge submissions. Edit : Done. Unluckily your python2 code should have got AC earlier, it seems that python2 is now slower than python3 for some tasks. Now you have AC in Python and Pike too. Last edit: 2013-03-09 13:43:24
	Fernando Fonseca [ITA]: 2013-03-09 13:31:16 For anyone using Python, you might want to read using sys.stdin.readlines(). I don't know what other tricks Francky used, but that got my code to barely pass the time limit. --ans--> I think Python3 is faster than Python2 for that problem. You make a good job, congratulations. Last edit: 2013-02-26 08:00:09
	preetam: 2013-03-09 13:31:16 guess a java solution is not even expected :P --ans-->My python3 code ran under 0.7s, so a java solution is possible, but with a good method only ! Last edit: 2013-01-29 19:06:59
	符号器: 2013-03-09 13:31:16 @Robert:what is your time complexity....i m doing in T(log(n)+log(k)) but still tle.... --ans(Francky)--> Sorry but I think we can't tell that answer ; constraints are set to allow efficient Py3 code to get AC in less than 0.7s, it is much faster with compiled language (but harder to write)... I recommend you to check your results first against a brute force Python solution, for example. Thanks for your participation. Last edit: 2013-01-21 14:56:10*
	Francky: 2013-03-09 13:31:16 @Robert : K=2 is included, sorry about that. ans: OK, got it, that was my last error. Last edit: 2013-01-21 13:09:26

Submit solution!

Added by:	Francky
Date:	2013-01-20
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own problem