标签 - BSGS

? 解题记录 ? ? BZOJ ? ? 二次剩余 ? ? BSGS ?    2018-12-19 10:52:32    566    0    0
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}\