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.

Input

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.

Output

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

Example

Input:
3
4
5
6

Output:
6
20
24

Constraints

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
Sushovan Sen: 2022-03-08 06:18:10

Getting WA. Cannot find error. Checked large prime numbers too. Seems ok to me. Any special cases?
(EDIT) -> Found bug, got AC.

Last edit: 2022-03-09 11:48:34
demacek: 2021-03-12 10:33:30

pleas give me a hint about my ID27545091 error

=(Francky)=> You have approx 8% of error on big random inputs ; you should find easily such examples with a semi brute force method. Good luck.

Last edit: 2021-03-13 15:49:41
ashish_k: 2020-06-20 13:39:41

(*** Edit ***)

=(Francky)=> No spoil in comments ; thanks. This is a problem, not anything.

Last edit: 2020-06-20 17:41:59
[Lakshman]: 2020-06-20 11:35:42

@ashish_k https://en.wikipedia.org/wiki/Pisano_period

ashish_k: 2020-06-20 10:42:12

can anyone give some hints for this question

soumya_dip: 2020-05-23 20:46:15

Please help me guys.I've got TLE,Can anyone give me some hint?

=(Francky)=> You need to learn how factorization could help with pisano. Brute force will not pass!

Last edit: 2020-05-24 09:15:35
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>.

edit:
--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

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