发布时间：2025-05-22

特征根法求递推式

假设$a_{n+2}=pa_{n+1}+qa_n$

令$x^2=px+q$，解出$x_1,x_2$

• $x_1\ne x_2$,$a_n=c_1x_1^n+c_2x_2^n$
• $x_1=x_2,a_n=(c_1n+c_2)x^n$

比如斐波那契数列，$x^2=x+1$,解得$x_1=\frac{1+\sqrt 5}{2},x_2=\frac{1- \sqrt 5}{2}$

$F_1=F_2=1$代入得，$F_n=\frac{\sqrt 5+5}{10}*(\frac{1+\sqrt 5}{2})^n-\frac{5-\sqrt 5}{10}*(\frac{1-\sqrt 5}{2})^n$

下面给出一个$O(\sqrt p)$预处理,$O(1)$查询的做法

对于根号直接求一个二次剩余

首先对指数$n$欧拉降幂，此时$n \lt p$

令$k=\sqrt p$,那么询问$n=kt+r(t,r \lt k)$,预处理$x^{kt}$和$x^r$

另外一种做法是像复数一样维护有根号的项