题解

$f(n)=af(n-1)+bf(n-2),f(1)=c,f(2)=d$

求$f(n) \ mod \ p$的最小循环节长度。

当$c$是模$p$的二次剩余时，枚举$n=p-1$的因子。

当$c$是模$p$的二次非剩余时，枚举$n=(p+1)(p-1)$的因子。

找到最小的因子$ans$，使得

$\begin{pmatrix} a & b \ 1 & 0 \end{pmatrix}^{ans}=\begin{pmatrix} 1 & 0 \ 0 & 1 \end{pmatrix} (mod \ p)$

具体证明见https://blog.csdn.net/ACdreamers/article/details/25616461

二次剩余的定义：

当存在某个$X$，使得式子$X^2=d (mod \ p)$成立时，则称$d$是模$p$的二次剩余。

当对任意$X$，式子都不成立时，称$d$是模$p$的二次非剩余。