Description
Fib数列为1,1,2,3,5,8...
求在Mod10^9+9的意义下，数字N在Fib数列中出现在哪个位置
无解输出-1
Input
一行，一个数字N，N < = 10^9+9
Output
如题
Sample Input
3
Sample Output
4
109+910^9+9明示55有二次剩余。
考虑FibFib的通项公式:
fn=1√5((1+√52)n−(1−√52)n) f_n=\frac{1}{\sqrt 5}\left (\left (\frac{1+\sqrt 5}{2}\
Rockdu's Blog