SPOJ.com - Problem FIB64

FIB64 - 64bit-Fibonacci

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!

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

hide comments

2013-06-03 01:24:54 Pranet Verma
i keep getting WA for some reason. its refusing to accept even for the first input line. can u please state the first line of the input? think im stuck due to constraints
edit: submission id 9405001 for cpp,9405009 for python

Last edit: 2013-06-03 01:26:47

2013-05-10 10:43:48 Arika Saputro
i use ME and tle, is it must use montgomery to get ac?
--ans--> Try with less input, just to check if you get AC or WA, after that you can experiment various ME methods. But before try to get AC, I think you're not ready. Take a look at constraints on m. ;-)
--ans--> oh, sorry i don't look if m until 10^18, nice, i think can get something new if solve this problem, thanks ;-)

Last edit: 2013-05-10 15:15:14

2013-04-30 12:58:59 [Lakshman]
Francky Please help me why WA again , I am trying to solve this problem for last 10 days but getting WA..again and again..I have tried several methods for solving this problem as well other Fibonacci problems and I got AC with same algo but can't figure out why getting WA here, Please help..
I have solve below fib problems.
Flibonakki, Arya Rage ,Fibonacci Sum...
--ans--> This problem is really different <-- the constraints on m. That's why this problem exists on its own. Good luck.

Last edit: 2013-05-10 11:38:04

2013-03-25 07:11:31 Michael Kharitonov
First to reach the limit:)
--ans--> Congratulations, I'll try in a test zone a new judge that take time into account, you need more points... I can't upload more data, there's a risk of SIGSEV.
--forw--> You can give the parameters of the input and output generator next time.
--ans--> No, it would allow cheaters to 'find' parameters and hardcode some answers ; I don't want to allow that possibility. But I'll find a good way, no doubt.
--forw--> If you change parameters every 1000 cases cheaters don't go far.
--ans--> It's a good idea, I though about it too, and for output, one can ask for XOR sum of each wave that give one point. It will be for another problem, I don't want to change here the needed base code to get AC.

Last edit: 2013-03-25 23:52:23

2013-03-20 11:18:58 Michael Kharitonov
I am getting close to the end of input;-)
--ans--> I see, and as I saw improvements, I hope I'll have answers on how to set a judge like PRIC that take into account if one can reach the limit. ;-) You'll do it soon...
--forw--> Am I right that I need to output exactly 33333333 chars as fast as possible to get high score in PRIC?
--ans--> I didn't reach yet the limit, but I think I know how. And I don't know what happen if one exceed the limit ;-)
And yes, that's the goal, after the limit, your score increase if you do less than 20s.

Last edit: 2013-03-20 12:32:19

2013-02-27 17:36:47 Francky
@ Michael Kharitonov : I don't know what to answer. Just many thanks for your great participation, I hope you'll enjoy my new challenge, and that all the 'fun' will join the party.
http://www.spoj.com/problems/MATEX/

2013-02-26 12:24:38 Michael Kharitonov
All the fun moved to the next Francky's problem(

2013-02-08 14:18:24 Francky
For your information my initial 331B python3 code get 10600 points with this new judge.

2013-02-08 02:12:13 (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†)
I just get VERY small points like an epsilon :-(
--ans--> The problem was made for you, remember. You got few points for now, but yet a much faster and correct code with your work. When someone work on PRIC he should know that it will probably give few points, too. The challenge is the same as in the beginning. With your work you will have a good place in the table rank, and that have no price.
EDIT(Tjandra): You're right, I forgot about PRIC problem, sorry for that.. Now this problem goal is "similar" to PRIC, so this problem isn't hard anymore (small limit to get AC)...
--ans2-->You'll can too try your experiments in python or in any language, for the fun, and the rank table per language as well.

Last edit: 2013-02-08 10:56:35

2013-02-08 00:10:32 Francky
Here is the new judge, new data, but I failed with masterJudge tuning. It will be for another problem, I need some tests to read time of submissions.
Edit : I think it's useless to rejudge.
--
How many points will you earn ?
Everybody will be able to get some with this new formula. Good luck !

Last edit: 2013-02-08 00:05:26