SPOJ.com - Problem PISANO

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.

Submit solution!

hide comments

< Previous 1 2 Next >

	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

Submit solution!

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