斐波那契循环节的简单根号做法-526互联

假设模\(p\)
考虑数对（向量）\(A_i=[F_i,F_{i+1}]\)，斐波那契数列的转移矩阵\(T\)
\(A_iT^k=[F_{i+k},F_{i+k+1}]\)
我们事实上要求出一个\(l\)，让\(A_1=T^lA_1\)（矩阵运算中，矩阵的元素均在模\(p\)意义下计算）。
考虑类似BSGS的做法：令\(k=floor(\sqrt{p})\)，\(A_1=A_1T^{ak+b},b<k\)
这等于\(A_1T^{-b}=A_1T^{ak}\)
枚举\(A_1T^{-b}\)，\(A_1T^{ak}\)，把它们放入哈希表内，并且求出这两个表的交集即可。
根据一个结论，斐波那契循环节的长度最多为\(6p\)，于是\(a\)只需要枚举到\(6\sqrt{p}\)。