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 >

	:.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
	Rishav Goyal: 2014-06-24 12:46:07 @Francky : i am getting WA after trying first testcase only. I think my solution is 100% perfect, but getting WA. Could you please tell me what's problem ? submission id : 11818146 --ans(Francky)--> Your solution is WA due to overflow issue when your are processing multiplications : a product of two 64-bit numbers can't fit in a 64-bit container. reply(Rishav) : ohh.!! ok ok got it . got it. Last edit: 2014-06-24 13:25:39
	Kishlay Raj: 2014-04-20 17:42:59 i got correct upto 5 , plz help me, i m not able to understand y is it not being able to solve more
	Kishlay Raj: 2014-03-07 18:25:51 is it that for case 5 100 we need to print something like 005 or just 5 will work. --ans(francky)--> The answer would be 5, and not 005. We are asked for a modulo result, not the last digit ; it could be, it's true, the same sometimes. I propose to check versus a brute force with Python ; you will see overflow problems in your code. Last edit: 2014-03-07 18:29:49
	Kishlay Raj: 2014-03-07 15:51:13 @Francky (thanks),when i m limiting my input to 50 its saying wrong answer and when i read all the inputs its saying TLE ,so is my solution wrong --ans--> It's true, your solution is wrong. Good luck. Last edit: 2014-03-07 16:02:45
	Kishlay Raj: 2014-03-05 06:51:08 solved in log n but still tle , any suggestions --ans(Francky)--> Don't try to read the whole input, it's too long. Read and solve only 50 lines and see what time it cost to you, after that increase... Last edit: 2014-03-05 09:18:31
	Shashi Kant Prasad: 2013-07-19 13:08:14 Last edit: 2013-12-10 17:05:08
	[Lakshman]: 2013-06-24 10:04:07 @Francky I did not get any point for this finally I solved this problem after long time. I really worked hard for this and deserve some points. I tried it in c,c++ java, Finally AC with python..Please Francky check this. --ans--> Did you read the warning : « This task is intended to help people to debug their codes and try speed experiments. ». Now you have an AC (in python) you'll can try experiments and find why your C code is wrong (it is indeed). Now I have AC code in c++ but very slow can only read 44000 inputs, But I am sure I can optimize it. I will find the way. Last edit: 2014-03-15 12:20:39

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