FIB128 - 128bit-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^38
2 <= M <= 10^38

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 FIB128-speed.


hide comments
damocris: 2024-05-20 07:40:49

any idea on this problem? pisano period? need to do integer factorization for the modular?

Paulo Roberto Santos de Sousa: 2019-04-08 05:07:54

is there some 256 bit integer in c/c++ or I will have to implement bigint algorithm to solve the problem?
=(Francky)=> You have. It's the game. Good luck,

Last edit: 2019-04-09 13:18:51
Fancy Mouse: 2017-11-09 12:50:53

pro tip: use clang. gcc optimization heuristics is horribly broken.

[Lakshman]: 2017-03-01 08:45:10

Why TLE. I am using ************, and on IDEONE I am getting correct output.
eg 1000000000000000000000000000000000000 1999999999999999999999999999999999999.

Thanks.

=(Francky)=> On my hardware (with Linux 64bit, GCC 5.4) you have TLE too even for a single input line. Curious. If you can, set a virtual machine using Manjaro beta, a Linux system that is very near of spoj engine, GCC 6.3 is provided by default, etc.
IDEONE != SPOJ engine.
Very curious indeed.
Solution : not inlining your fib function is giving correct answer, and no TLE. Your fib function inlined is very weird written...

Last edit: 2017-03-01 09:53:23
Michael Kharitonov: 2017-02-19 18:33:21

Yep, my method is a dead end, 10^38 is too much!
=(Francky)=> What a new challenge ! ;-)

Last edit: 2017-03-07 06:49:17

Added by:Francky
Date:2017-02-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:FIB64