fib数列

/dk

Posted by ShanLunjiaJian's Blog on February 23, 2022

整理了一些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 斐波那契

给\(a,b,m\),定义\(g_0=a,g_1=b,g_n=g_{n-1}+g_{n-2}\),求最小的\(p\)使得\(f_p\bmod{m}=0\)。\(10^5\)次询问,每次给出\(a,b\)而\(m\)不变,\(m\leq 10^5\)。

考虑crt,膜\(m\)为\(0\)等价于膜\(m\)的每个素因数幂都为\(0\),而膜每个素数幂都是一个环。