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 >

	[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. Thanks --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. ;p --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?
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-01-20 17:08:36 seems that my FRSKT solution doesn't work here... Now, time isn't problem anymore, the problem now is I'm getting WA... --ans--> For FRSKT, my Python code is faster than your C one, so there's some tricks to be found again... Here, now, I saw only few differences, you're near ... EDIT(Tjandra): Please doublecheck your test data.. My own algo that got AC in FRSKT getting WA here... ( Btw, now I know why my previous algo is slow ;-) ) --ans--> My data are well checked, I just found why your code fail... I'll set a new problem just for you ;-) It will be in challenge section, and it will be for speed addicts. EDIT(Tjandra): Thanks, finally got AC :-D Last edit: 2013-01-20 21:13:56

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