SPOJ.com - Problem FIB64

FIB64 - 64bit-Fibonacci

no tags

Warning

This task is intended to help people to debug their codes and try speed experiments.

The task is the same as in some known problems, but with new constraints and speed goal.

The Fibonacci sequence is defined for any positive integer by :
If N<2: Fib(N)=N, else Fib(N)=Fib(N-1)+Fib(N-2)

You have the task of being the fastest to compute Fib(N) mod M.

Input

The input consists of 500,000 lines.
In each the 500,000 lines there are two integers N, M.
You don't need to read the whole input, only some lines to get some points.
You should begin with one line, then 10, then 100, ...

Output

For as many test cases you can, on a single line, print Fib(N) mod M.

Example

Input:
5 4
5 5
5 6
[...]

Output:
1
0
5

Constraints

0 <= N <= 10^18
2 <= M <= 10^18

Score

As in the example, if you can output the 3 first correct answers, your score will be 3 points. No need to solve all the input, the minimum is 1 ; every solver in any language will be able to check his FIB64-speed.

Submit solution!

hide comments

< Previous 1 2 3 4 Next >

	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-02-08 00:10:32 It's up to you, but with that scoring as the challenge scoring is relative to the top score I'll only get 1/7=0.2857 points from this problem (because my program speed is 7x slower than the top score)... (feel bad if 8 hours work just earn only 0.2857pts).. Compared to If this problem moved to classical: score = 80/(40+(2 solver))=1.9047 points (I satisfied with this).. My goal now on SPOJ is to get around 300-350pts (world rank #10-#20)... And again it's up to you.. I just don't want that hard problem give less points compared to easy problem that give many points (e.g. Man of Steel)... Anyway, thanks for this problem, this problem give me more knowledge about how to fibonacci more efficiently.. Last edit: 2013-02-07 19:51:22
	Francky: 2013-02-08 00:10:32 OK, there's still a problem with score. I don't want to put it in classical, as the goal is purely speed here. I'll write a new own judge and score will be number_of_solved_cases / (time+0.01) ; maximize score ; any wrong answer -> WA. I think I'll try to upload 10× more input/output, and give ×10 more time, this will make more accurate scoring. @ all : Do you agree with that proposition, or do you see better ?
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-02-08 00:10:32 @Francky: all score=0, I got no point from this problem.. imho it's better to set the judge to binary, and move this problem to classical (In fact, this problem is hard because in last 19 days, only 2 SPOJ users solve this problem)...
	Francky: 2013-02-08 00:10:32 Assessment type had been changed to "minimize score". Hope that now it counts as a challenge. Thanks for having pointed this out. Last edit: 2013-02-07 08:48:01
	Aditya Pande: 2013-02-08 00:10:32 shall o(log n) pass in python --ans--> Yes, it's not a secret, there's no other way here, but the constant will be a little tight in Python. edit: thank you Last edit: 2013-01-23 07:47:30
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-02-08 00:10:32 Phew... finally AC after ~4 hours working... luck 0.99s :-) Thanks Francky, for 1s time limit... EDIT: found new faster trick to compute fibonacci ;-) for now 0.49s is my best speed... I wonder how can Robert Gerbicz solve this problem in 0.07s (exactly 7x faster than mine)... EDIT2: seems that no case with m<10^14 Last edit: 2013-01-22 03:10:44
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-02-08 00:10:32 Based on my experiment, my speed is 0.6s+0.6s=1.2s... need speed up about 17% to get AC... Last edit: 2013-01-21 17:58:16
	Robert Gerbicz: 2013-02-08 00:10:32 Fast reading/writing gives no speedup.
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-02-08 00:10:32 Haha, very nice, I can't solve it using C, now I'll work with python.. EDIT: Time limit too strict for me.. --ans--> So it's a good challenge, isn't it ? My 1/3kB of py3 got AC in 0.93s, there's still many optimization rooms for python, and much more in C... EDIT: Yes, it's really challenging.. Because it possible to get accepted with python3 code and also hard for fast language, maybe someday I can solve this problem after overclocking my brain... now I'm out of idea... Last edit: 2013-01-20 23:36:36
	Francky: 2013-02-08 00:10:32 @tjandra : What about a fundamental little test ?

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