Z124  Zeros in Fibonacci period
Perhaps the first thing one notices when the Fibonacci sequence is reduced mod p is that it seems periodic.
For example :
F (mod 2) = 0 1 1 0 1 1 0 1 ...
F (mod 3) = 0 1 1 2 0 2 2 1 0 1 1 2 ...
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 Z(p) the number of zeros in fundamental period of Fibonacci numbers mod p (if it is periodic).
We just saw that Z(2) = 1, Z(3) = 2, and Z(5) = 4.
Input
The first line contains T, the number of test cases.
Each of the next T lines contains a prime number p.
Output
For each test case, print Z(p), or "Not periodic." without quotes if need.
Example
Input: 3 2 3 5 Output: 1 2 4
Constraints
1 < T < 10^5 1 < p < 10^18, a prime number
There's two input files, in the first one you are given all primes under 10^6, in the second one lot of uniform randomly chosen primes.
Warning : Time limit had been changed, and could not allows slow languages to get AC here. This problem allows easy coding using languages without bigNum library, but you need to be able to get at least some few points at FIB64.
My best Ctiming is 0.12s. (Edit : 0.03s with cluster change)
For other languages, take a look at Z124H with higher constraints.
Good luck, and have fun ;)
hide comments
liouzhou_101:
20170829 10:14:51
Finally, I've beaten your time, Michael Kharitonov!


Michael Kharitonov:
20170131 23:24:02
Finally, I've beaten your time, Francky!


[Lakshman]:
20160724 15:22:58
Okay I got AC. Now I am able to pass the time limit, But for some P my algorithm still depends of Finding Pisano and this part is consuming most of the execution time. Still am in search of the optimal algorithm. Last edit: 20160724 15:23:22 

[Lakshman]:
20160723 21:11:20
Need One help, My I know for which input file I am getting TLE or getting TLE in both. Thanks.


[Lakshman]:
20160723 15:55:21
Good Problem, But My algorithm is just a mess. I think there is some simple algorithm to solve this.

Added by:  Francky 
Date:  20160721 
Time limit:  0.25s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 