PISANO - Modular Fibonacci Period

no tags 

Perhaps the first thing one notices when the Fibonacci sequence is reduced mod M is that it seems periodic.

For example :
F (mod 4) = 0 1 1 2 3 1 0 1 1 2 3 ...
F (mod 5) = 0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 2 3 ...

We define K(M) the period of the Fibonacci sequence reduced mod M if it is periodic.
We just saw that K(4) = 6 and K(5) = 20.


The input begins with the number T of test cases in a single line.
In each of the next T lines there are one integer M.


For each test case, on a single line, print K(M), or "Not periodic." without quotes if need.





1 < T < 10^4
1 < M < 10^12

Edit 2017-02-11, after compiler changes ; new TL. My old Python code end in 1.92s.

hide comments
Erick Leonardo de Sousa Monteiro [UEA]: 2019-11-14 13:55:36

Had to use __int128_t to pass. Good problem.

sanyam19: 2018-06-10 11:06:32

i am getting tle. ID 21811838

=(Francky)> The complexity of your code is O(T×M²), and several 10²⁸ operations can't be processed in decent time. You need to find another method than brute force.

Last edit: 2018-06-11 00:09:49
waddlepoof: 2014-07-28 21:56:33

haha, I had an overflow error...

waddlepoof: 2014-06-25 19:44:25

I do not know if I totally missed the point or if current version of GHC being 32-bit is a great impact on performance, because on my incredibly slow computer I've managed to decrease running time from 49 seconds to 5 seconds for 10000 randomly generated [1..10^12] integers.
--ans(Francky)--> I recommend you to post a new message <a href="http://www.spoj.com/forum/viewtopic.php?f=53&t=11555&p=41673&hilit=ghc&sid=aa74f711b139e3567a9100c957f351b7#p41673">here</a>.

--ans(waddlepoof)-->Thanks, but still, there are fast Haskell solutions and I have WA on some of my submits so maybe there's still room for improvement.

Last edit: 2014-06-26 17:52:50
[Lakshman]: 2014-05-01 11:46:47

@Francky I think I have correct solution but getting WA can you help me? if I am doing something wrong.
--ans(Francky)--> If you try some random cases, you'll see that some of your answers are negative, and many of them are way to high. It is easy to build a brute force (but very slow) and compare. You have a lot of WA, and you should have detect that by your own. Good luck, I'm sure you'll find many interest in the task.

--Lakshman--> Can I have some sample case where I am getting WA.
--Francky--> You should build a brute force, you still have a non small % of WA on random cases (say 25%). You still have negative outputs on rare tricky cases. No other cases are provided as you can easily build them ;-) good luck.

Last edit: 2014-05-03 11:41:47
Federico Lebrón: 2013-06-27 20:56:31

This was a lot of fun, thanks!

Haskell AC took me some time, partially because Integer is slow, but mostly because I'm pretty clueless. I had to learn quite a few new things to tackle this one, so again many thanks!

--ans--> Thanks for your comment, the problem was designed to be feasible with slow languages ; my old python code got AC under 4s.

Last edit: 2013-06-27 22:54:11
Damian Straszak: 2013-02-20 23:04:18

Nice problem. Unfortunately I wasn't able to get AC in Python. This is because my solutions still needs some brute-force to work.
--ans(Francky)--> I just can tell that your Python code fails under 10% of test cases, but I can't tell you why. Good job and thanks for appreciation. With your C solution that get AC, no doubt you'll can debug your Python code if you want to.
--ans(Damian)--> This is because I was submiting a wrong solution to benchmark time ;) Actually I have a correct Python solution but it is like 50% to slow.

Last edit: 2013-02-21 17:01:24
Ninja coder: 2013-01-28 09:47:58

@Tjandra: My code seems to be smaller than your comment.
--ans(Francky)--> But I don't think that a such small code can get AC, try it and we will be fixed. ;-)

Last edit: 2013-01-28 10:09:14
Ehor Nechiporenko: 2013-01-24 12:08:50

Francky, thanks a lot for this problem! It was a great enjoy for me to solve it!
--ans--> Sorry for late answer, I was very very busy. Congratulations and thanks for your appreciation.

Last edit: 2013-01-25 17:32:27
Ehor Nechiporenko: 2013-01-23 22:40:55

Hey Francky, do you have a tricky tests with big prime numbers, like a 999999999989?

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