FIB64  64bitFibonacci
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(N1)+Fib(N2)
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 FIB64speed.
hide comments
nadstratosfer:
20191207 03:32:40
Dune, compilers were updated on 20190724. Not sure about compiler options for CPP14, but I have noticed 1) Python 2 can no longer get 0.00s, even with an empty source and 2) I can't beat some old top times in kind of problems I'm confident I previously would have. So my guess is, there's a slight slowdown, whatever the reason. 

Dune:
20191206 19:28:43
There is a slowdown with the new CPP14 compiler or with the compiler options: my CPP14 solution with 961538 points running in 0.51 sec runs now at 769230 points in 0.64 sec. I notice a slowdown consumption memory from 34MB to 10MB. Is there compilator options changed? 

imadg:
20180331 12:57:22
Getting WA!


Curiosa:
20171016 13:21:29
@Francky, can this problem be solved with the approach I have right now? I mean just optimizing the constant. I have other ideas but I don't know if tehy're worth investing time in.


Michael Kharitonov:
20170214 02:29:30
What about rejudge? Can you upload more tests (with the same number of lines) for more accuracy? Maybe round score to whole number, it'll be more than enough.


Francky:
20170212 17:53:14
New MasterJudge : IF score == 500000 THEN score /= 0.01+yourTime/maxTime


Michael Kharitonov:
20170212 14:21:30
Latest C/C++ compilers update really sped up my solution.


Min_25:
20160818 17:21:06
The cube cluster has been migrated to a new server Intel(R) Xeon(R) CPU E31220 v5.


Min_25:
20160519 04:20:18
Note: We can complete the task without the inline assembler.


:.Mohib.::
20150704 15:50:51
@Francky can you please check my submission I think it's correct but WA here :(

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