Its from codechef.com, I'm eager to learn different approaches. I came up with this after a lot of tries but still the performance is slow.
It is required to find the minimum n such that Fn % p = c.
Fn is the nth fibonacci term, ct is n in this code.
Range of c, 0 ≤ c ≤ p-1
p is a prime number <2000000000 and also p % 10 is guaranteed to be a perfect square. Can this property be used in any way to optimize instead of just brute-forcing?
Thanks.
I observed the results of mod p on Fibonacci series and noticed that they repeat themselves after a certain count (the count most of the times being p-1) and so wrote this code but it still isn't optimal, for the prime 1999999871 it loops until 1999999870.
Does p%10 being a perfect square help??
1) you are doing it all wrong.
From equation F_{n} % p = c → F_{n} = x·p + c where x ∈ N
From numbers less than p you need to check only c itself. Next one will be p+c, then 2·p+c etc.
You might want for each t = x·p + c to check if it is a fibonacci number using known formulas, calculate n of said number using other formulas and output that number.