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.


hide comments
imadg: 2018-03-31 12:57:22

Getting WA!
Don't know what I'm doing wrong!!
submission id: 21447595

=(Francky)=> You have overflow issue when multiply to 64bit numbers, the answer is a 128bit number and don't fit in a 64bit container. That's the point of the problem. Good luck.

Last edit: 2018-03-31 16:29:07
Curiosa: 2017-10-16 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.

=(Francky)=> It's now a matter of optimizing the constant, there's a lot of room for experiments. Have fun.

Last edit: 2017-10-16 22:27:53
Michael Kharitonov: 2017-02-14 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)=> We can't (for now) rejudge. Maybe admins plan that in near future. Yes, I can round score, and add some new IO files. I will set FIB128 as well.
Edit : ready => http://www.spoj.com/problems/FIB128/

Last edit: 2017-02-15 00:12:07
Francky: 2017-02-12 17:53:14

New MasterJudge : IF score == 500000 THEN score /= 0.01+yourTime/maxTime
Does that suit ? Have fun ;-)

Michael Kharitonov: 2017-02-12 14:21:30

Latest C/C++ compilers update really sped up my solution.

=(Francky)=> Yes, I've quite finished to finely tune new TL for my classical problems. For my challenges, I'll use a master_judge that will take into account those who reach the limit. The challenge continue. I don't know yet if a rejudge will be done. I'll inform of what I'll can. I'll post a new message when master_judge will be on.

Last edit: 2017-02-12 14:51:28
Min_25: 2016-08-18 17:21:06

The cube cluster has been migrated to a new server Intel(R) Xeon(R) CPU E3-1220 v5.

=(Francky)=> I was offline those days ; I'll set a new master judge to take into account ultra fast solutions ; as I promised. Congrats again.

(Re) Thank you for everything.

Last edit: 2016-08-21 14:48:29
Min_25: 2016-05-19 04:20:18

Note: We can complete the task without the inline assembler.

=(Francky)=> Congratulations! And it's true ; the top three solutions don't have inline assembler ; it's a hard task!

Last edit: 2016-05-19 09:04:43
:.Mohib.:: 2015-07-04 15:50:51

@Francky can you please check my submission I think it's correct but WA here :(

=(Francky)=> Your answer is a negative number ; impossible ; so you have WA on your last code that output this single number. You have critical issue in your code, I recommend you to use python first to debug. Good luck.

Last edit: 2015-07-04 17:00:45
the_new_kid: 2015-06-15 13:54:18

@Francky I am getting accepted at 2890 and TLE at 2900. Can you please help me handle the 64 bit product problm? I am doing addition and bitwise operations to perform the addition and matrix exponentiation to get the Fibonacci. What am I missing? Isn't log(n) fast enough?

(Francky) => It is definitively log(n), but there's many constant optis to be found. No advice here. Good luck.

Last edit: 2015-06-15 14:34:47
[Lakshman]: 2014-12-10 16:02:11

I got the new Idea for this problem that works much faster for this problem.


EDIT1:: Now my code is much faster and can read 207999 lines now on #5 place.
EDIT2:: 240000 lines now.

Last edit: 2014-12-26 04:58:40

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