整理了一些fib数列相关的经典问题和trick。
fib数列是$f_0=0,f_1=1,f_i=f_{i-1}+f_{i-2}$。
(OI中常见的)广义fib数列是$f_0,f_1,a,b$是任意值，$f_i=af_{i-1}+bf_{i-2}$的数列，不妨称为$a,b$-fib数列。$a,1$-fib数列是限制$b=1$的情况，单独把它提出来是因为它在循环节上有很好的性质。普通的fib数是$1,1$-fib数的一种。
经典式子
\[F=\frac{z}{1-z-z^2},f_n=\frac{1}{\sqrt{5}}(\phi^n-\hat{\phi}^n)\]众所周知。
\[\begin{bmatrix} f_n\\ f_{n-1} \end{bmatrix} = \begin{bmatrix} a&b\\ 1&0 \end{bmatrix} \begin{bmatrix} f_{n-1}\\ f_{n-2} \end{bmatrix}\]给出$a,b$-fib数的矩阵快速幂算法。
对于一个$a,b$-fib数列，如果初值不是$f_0=0,f_1=1$，那么设$f^\prime$是初值是$f_0=0,f_1=1$的$a,b$-fib数列，有
\[f_n=f_0f^\prime_{n-1}+f_1f^\prime_{n}\]。归纳容易证明。
对于$a,b$-fib数，有
\[f_{n+1}f_{n-1}-f_n^2=(-b)^{n-1}(bf_0^2+af_1f_0-f_1^2)\]，这被称为卡西尼恒等式。
一个非常简单的证明来自那个矩阵快速幂做法。或许你可以认为它就是这么来的。
\[\begin{bmatrix} a&b\\ 1&0 \end{bmatrix}^{n-1} \begin{bmatrix} af_1+bf_0&f_1\\ f_1&f_0 \end{bmatrix} = \begin{bmatrix} f_{n+1}&f_n\\ f_n&f_{n-1} \end{bmatrix}\]两边取行列式就得到上面的恒等式。如果你观察过$1,1$-fib数的转移矩阵自己快速幂的结果，你可能也会发现这个。如果你真的很无聊，对它两边取det，你就独立发现了卡西尼恒等式。
对于$f_0=0,f_1=1$的$a,1$-fib数，它特化为
\[f_{n+1}f_{n-1}-f_n^2=(-1)^n\]。你可以在具体数学上看到这个。这个东西居然真的有用/jy，一会我们真的会用到它。
感谢 vectorwyx 的指导。
对于$1,1$-fib数列$f$，设普通fib数列为$f^\prime$(它俩的区别在于一个初值任意一个初值是$f_0=0,f_1=1$)，有
\[f_{n+k}=f^\prime_{k-1}f_n+f^\prime_kf_{n+1}\]。这个非常经典，可以不断展开来证明。如果这个$f$就是普通fib数列，这一结论可以扔掉$^\prime$而特化为
\[f_{n+k}=f_{k-1}f_n+f_kf_{n+1}\]。一个经典推论是，取$n=m$，得到
\[f_{2n}=f_n(f_{n+1}+f_{n-1})\]同理有
\[f_{3n}=f_{2n-1}f_n+f_{2n}f_{n+1}\]于是我们知道所有$f_{kn}$都是$f_n$的倍数。经典用法是$\gcd(f_n,f_m)=f_{\gcd(n,m)}$。
它的逆也是成立的，也就是说$f_n\mid f_m\Leftrightarrow n\mid m$。
对于$a,b$-fib数，我们考虑了一下，结论好像会很复杂。
fib循环节
fuck，找不到来源论文了/fn
循环节和初值往往没有很密切的关系。
定理1 $a,b$-fib数列膜素数$p$的循环节，设为$\pi(p)$，不超过$2p\operatorname{ord}_p(-b)$。
证明 考虑广义fib数的特征多项式$q(z)=z^2-az-b=(z-\alpha)(z-\beta)$，其中$\alpha,\beta=\displaystyle\frac{a\pm\sqrt{a^2+4b}}{2}$。
-
根据有理展开定理，如果$\alpha\neq\beta$，那么有$f_n=A\alpha^n+B\beta^n$，其中$A,B$是某些常数。
-
case1 : 如果$\alpha,\beta$在膜$p$下存在，那么根据费马小定理，$\alpha^{p-1}\equiv 1\pmod{p},\beta^{p-1}\equiv 1\pmod{p}$，于是$\pi(p)\mid p-1$。
-
case2 : 如果$\alpha,\beta$在膜$p$下不存在，注意到由于$\displaystyle\alpha=\frac{a}{2}+\frac{\sqrt{a^2+4b}}{2}$，而经典结论指出$(x+a)^p\equiv x^p+a\pmod{p}$，于是你发现$\displaystyle\alpha^p\equiv\frac{a+(a^2+4b)^\frac{p-1}{2}\sqrt{a^2+4b}}{2}$。由于$a^2+4b$不是二次剩余(否则刚才讨论过了)，$\displaystyle(a^2+4b)^\frac{p-1}{2}=-1$。这说明$\alpha^p\equiv\beta$，而根据韦达定理又有$\alpha\beta=-b$，于是$\alpha^{p+1}\equiv -b$，于是$\alpha^{(p+1)\operatorname{ord}_p(-b)}\equiv 1$，那么$\operatorname{ord}_p(\alpha)\mid (p+1)\operatorname{ord}_p(-b)$的因数。同理$\operatorname{ord}_p(\beta)\mid (p+1)\operatorname{ord}_p(-b)$的因数，于是$\pi(p)\mid (p+1)\operatorname{ord}_p(-b)$。
-
-
case3 : 如果$\alpha=\beta$，那么有$f_n=(A+Bn)\alpha^n$，其中$A,B$是另一些常数，并且$\displaystyle\alpha=\frac{a}{2}$必然存在。这种情况出现，当且仅当$p\mid a^2+4b$。$A+Bn$的循环节是$p$(由于$p$是素数，这玩意是紧的)，$\alpha^n$则需要观察一下。因为$a^2+4b\equiv 0$，所以$\displaystyle\left(\frac{a}{2}\right)^2\equiv -b$，于是$\operatorname{ord}_p(\alpha)\mid 2\operatorname{ord}_p(-b)$，于是$\pi(p)\mid 2p\operatorname{ord}_p(-b)$。
推论1 $a,1$-fib数列膜素数$p$的循环节不超过$4p$，$a,-1$-fib数列不超过$2p$。
证明 直接推论。
引理0.5 如果$x\equiv 1\pmod{p}$，那么$x^{p^{k-1}}\equiv 1\pmod{p^k}$。
证明 感谢洛谷用户 @论文 和我校mo爷Fanzor的指导。
升幂定理。当$p$是奇素数，有$\nu_p(x^{p^{k-1}}-1)=\nu_p(x-1)+\nu_p(p^{k-1})=\nu_p(x-1)+k-1\geq k$。当$p=2$，有$\nu_2(x^{p^{k-1}}-1)=\nu_2(x-1)+\nu_2(x+1)+\nu_2(2^{k-1})-1\geq k$。
引理1 对于任意常系数齐次线性递推定义的数列$a$，设$a$膜$m$的循环节是$\pi(m)$，那么对于素数幂$p^k$有$\pi(p^k)\mid\pi(p)p^{k-1}$。
证明 考虑任意常系数齐次线性递推定义的数列，根据有理展开定理，它的解必然是$f_n=\sum A_i(n)\alpha_i^n$，并且感觉一下，每个$A_i(n)\alpha_i^n$膜$p$的循环节都是$\pi(p)$的因数。
把$A_i(n)$拆成若干$n^e$的线性组合，它们膜$p$的循环节显然是$p$的因数，并且它也是$\pi(p)$的因数，所以它必然是$\gcd(p,\pi(p))$的因数，所以膜$p^k$的循环节必然是$\gcd^k(p,\pi(p))\mid\pi(p)p^{k-1}$的因数。
同时根据引理0.5，我们知道$\alpha_i^n$膜$p^k$的循环节是$\pi(p)p^{k-1}$的因数，所以就证完了。
推论2 fib数列膜任意数$m$的循环节，设为$\pi(m)$，不超过$6m$。
证明 考虑$\pi(m)=\mathop{\mathrm{lcm}}\limits_{p^k\parallel m}\pi(p^k)$，而根据引理1有$\pi(p^k)\leq p^{k-1}\pi(p)$。直接给结论1代入$\operatorname{ord}_p(-b)=2$。
当$a=b=1$时，case2出现当且仅当$p\equiv\pm 2\pmod{5}$，case3出现当且仅当$p=5$，而$\pi(5)=20$。同时我们没有讨论$p=2$的情况，容易知道$a=b=1$时$\pi(2)=3$。所以可以构造一下，最大值在$m=2\cdot 5^k$时取到，此时$\pi(m)=6m$，同时容易证明其它情况都有$\pi(m)\leq 4m$。
fib数比起广义fib数，膜任意数下循环节都很小，这是因为它的$a^2+4b$非常小，以至于特殊情况非常少。
下面是一些例题。
要寻找任意广义fib数列的循环节，我们可以做到$O(\sqrt{m})$。上一个pr找到所有素因数，然后对于一个素因数$p^k$，需要对一个$O(p^2)$的数跑pr，然后对每个因数做一次矩阵快速幂，然后对每个素因数取$\mathrm{lcm}$，可以考虑使用k进制快速幂。总复杂度看起来是$O(\sqrt{m}+d(m))$，后者比较低阶可以扔了。
如果是膜素数$p$的循环节，并且$\operatorname{ord}_p(-b)$比$p$低阶，那么复杂度降为$O(\sqrt[4]{p\operatorname{ord}_p(-b)})$。此时使用k进制快速幂做到$O(1)$的判断，看起来对常数很有帮助。
如果$m$很小，简单做法是随一随然后floyd找环，期望复杂度是$O(\sqrt{m})$。或者你也可以把pr换成爆力，复杂度是$O(\frac{\sqrt{m}}{\log m})$，看起来要更棒一些。很多题其实只需要后者。
有经典题如下。
求$a,b$-广义fib数列的值$f_n$，膜任意数$m$。$n\leq 10^{10^7},m\leq 10^{12}$。
直接上板子，求出循环节之后，把$n$对循环节取模，然后矩阵快速幂。复杂度$O(\sqrt{m}+\log n)$。
求$a,1$-广义fib数列的值$f_n$，膜任意数$m$。$n\leq 10^{10^7},m\leq 10^{18}$。
直接上板子，求出循环节之后，把$n$对循环节取模，然后矩阵快速幂。复杂度$O(\sqrt[4]{m}+\log n)$。
给膜$p$下$a,1$-广义fib数列中相邻的两个值$A=f_n,B=f_{n-1}$，求$n$在一次循环中可能的值。$p\leq 10^{11}$。
先求出循环节，然后我们考虑，这是要求
\[\begin{bmatrix} a&1\\ 1&0\\ \end{bmatrix}^n \begin{bmatrix} f_1\\ f_0 \end{bmatrix} = \begin{bmatrix} A\\ B \end{bmatrix}\]注意到这个矩阵是有逆的，看起来这个逆是$\displaystyle\begin{bmatrix}0&1\1&-a\end{bmatrix}$。考虑bsgs，我们把它变成
\[\begin{bmatrix} a&1\\ 1&0\\ \end{bmatrix}^s \begin{bmatrix} f_1\\ f_0 \end{bmatrix} = \begin{bmatrix} a&1\\ 1&0 \end{bmatrix}^{tK} \begin{bmatrix} A\\ B \end{bmatrix}\]，然后就$O(\sqrt{p})$了。
如果膜数是合数呢?一样做。
hdu5848 mutc2016 contest9 E. Easy Homework
给$a,x,p,l,r$，求膜$p$下$a,1$-广义fib数列($f_0=0,f_1=1$)的区间$[l,r]$中值$x$的出现次数。$a,p\leq 10^9,l,r\leq 10^{18}$，$120$组数据。
刚才我们做了两个值的问题，可是这里只有一个值啊?
考虑一个牛逼想法，我们用那个卡西尼恒等式。这给出$f_{n+1}f_{n-1}-f_n^2=(-1)^n$，代入递归式得到$(f_n+f_{n-1})f_{n-1}-f_n^2=(-1)^n$，解得$\displaystyle f_{n-1}=\frac{-f_n\pm\sqrt{f_n^2+4(f_n^2+(-1)^n)}}{2}$。枚举$n$的奇偶性，我们可以得到四个解，扔个cipolla把它们求出来，然后套上面的bsgs就好了。如果那个根号开不出来，或者说它不存在，那么可以舍掉这个解(而不用二次扩域去算)，因为fib数总是整数，不会出现膜意义下不存在的情况。
总复杂度$O(T\sqrt{p})$。一共要跑四遍bsgs/xia
一个常数优化是，注意到$f_0,f_1$是不变的，它那边只需要跑一遍，另一边跑四遍，这样就从八遍枚举变成了五遍枚举。
wc2021 斐波那契
«««< Updated upstream 给$a,b,m$，定义$f_0=a,f_1=b,f_n=f_{n-1}+f_{n-2}$，求最小的$p$使得$f_p\bmod{m}=0$。$10^5$次询问，每次给出$a,b$而$m$不变，$m\leq 10^5$。
设$f^\prime_n$是普通fib数列，那么$f_n=af_{n-1}+bf_n$。
考虑素数怎么做。$af_{n-1}+bf_n=0$，也就是$-\frac{a}{b}=\frac{f_n}{f_{n-1}}$。把$b$取负。
考虑一般情况怎么做。来点强力做法，我们还是看$af_{n-1}=bf_n$这个式子，提个$\gcd$，看起来我们要想把$b$除过去，就要先和左边和$m$同除一个$\frac{m}{\gcd(b,m)}$，所以就提它，但是我们不一定能提它，因为它不一定是左边的因数，得到$\frac{a}{g}f_{n-1}=\frac{b}{g}f_n\bmod{\frac{m}{g}}$。
======= 拜谢 https://www.luogu.com.cn/blog/138400/solution-p7325 。
给$a,b,m$，定义$f_0=a,f_1=b,f_n=f_{n-1}+f_{n-2}$，求最小的$p$使得$f_p\bmod{m}=0$。$10^5$次询问，每次给出$a,b$而$m$不变，$m\leq 10^5$。
既然$a,b$会变，我们考虑能不能把它们提出来，发现还真可以，设$f$是普通的fib数，那么题中的$f_n$就是$af_{n-1}+bf_n$，考虑转移矩阵容易得到这个结论。
所以我们其实是求解$af_{n-1}=bf_n\pmod{m}$这样的东西，这里把$a,b$之一取负了。
那么一个很自然的想法是把$a,b$放到一边，$f_n,f_{n-1}$放到一边，也就是变成$\frac{a}{b}=\frac{f_n}{f_{n-1}}\pmod{m}$，但是这里不一定互素。一个稍微有点经典的性质是$f_{n-1},f_n$必然互素，证明考虑辗转相除的过程。
考虑我们希望$\gcd(b,m)=\gcd(f_{n-1},m)=1$，先给三边都除掉$\gcd(b,m)$，因为它整除右边，所以它也一定整除左边，所以我们把左边除掉它，那么现在我们可以把$\frac{b}{\gcd(b,m)}$移过去了。但是这导致我们必须把$af_{n-1}$看成一个整体来除掉它，这就很不好，所以考虑先除掉$\gcd(a,b,m)$，那么此时必然有$\gcd(a,\gcd(b,m))=1$，所以它就是$a\frac{f_{n-1}}{\gcd(b,m)}=\frac{b}{\gcd(b,m)}f_n\pmod{\frac{m}{\gcd(b,m)}}$。
然后我们除掉一个$\gcd(\frac{f_{n-1}}{\gcd(b,m)},\frac{m}{\gcd(b,m)})$，就可以把$f_{n-1}$移过去了。但是这里同时和$b,f_{n-1}$相关，这就是寄了。但是我们刚才知道$\gcd(f_n,f_{n-1})=1$，那么到这一步了必然有$\gcd(f_{n-1},\frac{m}{\gcd(b,m)})=1$，因为如果$>1$，因为两边相等它必然也是右边的因数，那就和$\gcd(f_n,f_{n-1})=1$矛盾了。所以可以直接除过去。
那么要对一个$m$预处理，首先枚举$\gcd(a,b,m)$，它必然是$m$的因数，然后枚举$\gcd(\frac{b}{\gcd(a,b,m)},\frac{m}{\gcd(a,b,m)})$，它是$\frac{m}{\gcd(a,b,m)}$的因数，这样看来我们的复杂度就是因数的因数和，然后hash table一下就好了。我们知道因数和不超过$O(m\log\log m)$，所以是$O(m(\log\log)^2 m)$的。
继续注意到有$\gcd(\frac{b}{\gcd(a,b,m)},\frac{m}{\gcd(a,b,m)})=\gcd(\frac{f_{n-1}}{\gcd(a,b,m)},\frac{m}{\gcd(a,b,m)})$，所以对于每对$(f_{n-1},\gcd(a,b,m))$，只有一个确定的$\gcd(\frac{b}{\gcd(a,b,m)},\frac{m}{\gcd(a,b,m)})$，这样其实只需要往hash table里插$O(m\log\log m)$个数。瓶颈在于和$m$的因数求$\gcd$，通过记忆化$\gcd$可以做到$O(m\log\log m)$。查询只需要求$\gcd$，刚才已经预处理所以是$O(1)$的，那么总复杂度就是$O(m\log\log m+q)$。
Stashed changes