Z124 - Zeros in Fibonacci period

no tags 

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.


The first line contains T, the number of test cases.
Each of the next T lines contains a prime number p.


For each test case, print Z(p), or "Not periodic." without quotes if need.





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 C-timing 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: 2017-08-29 10:14:51

Finally, I've beaten your time, Michael Kharitonov!

............only on Z124H

Michael Kharitonov: 2017-01-31 23:24:02

Finally, I've beaten your time, Francky!

=(Francky)=> I'm very happy to see you again. I'll change a master judge in some problems of mine in challenge section (eg FIB64) where you're involved. As some users got the top score, the challenge will continue !
Congrats for your hyper fast submissions ;-)

=(Michael)=> By the way, code straight from Z124H got accepted here! 10 times slower than ad hoc code. And after 4 long years I'll finally make use of the BINARYIO problem!

Last edit: 2017-02-19 15:35:14
[Lakshman]: 2016-07-24 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: 2016-07-24 15:23:22
[Lakshman]: 2016-07-23 21:11:20

Need One help, My I know for which input file I am getting TLE or getting TLE in both. Thanks.

=(Francky)=> For 17349240, you have TLE at 1st input file. Good luck. You should find a way without factorisation.

=(Lakshman)=>Is it not the Time Limit a bit strict for small input file, it should be around .50.

=(Francky)=> For input1, my t is 0.05s, BM's code is at 0.13s (desired solution ; basic IO), TL is at 0.25s. For me it's fine : ×5 my t.
For input2, my t is 0.07s (using fast method), BM at 0.57, TL is 1s. For me it's fine. Good luck.

Last edit: 2016-07-24 02:31:26
[Lakshman]: 2016-07-23 15:55:21

Good Problem, But My algorithm is just a mess. I think there is some simple algorithm to solve this.
=(Francky)=> Good job ; It's true, there's a much simpler method, that allows very huge prime in input ; I've let p<10^18 only for (languages_without_bignum_lib)-users. Maybe I should move this one to tutorial (or reduce TL for this one, but sad for Python user here), and set a classical edition with p<10^100. In that case, only the desired method would get AC.
Please share your thoughts about that.
@BlueMary : You're invited too, to ask for another edition, if you want.

==(Lakshman)==> I don't think it is easy at all. Yes and Time limit can be reduced for this and still this is relevant in classical section(for users who don't use python). A new Problem with new constraints(as you have suggested) would be better option for Python users.

=(Francky)=> Done. Thanks for your reply.

Last edit: 2016-07-23 20:10:45

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