OI Wiki 斐波那契数列全解通项公式、快速计算、斐波那契编码与 Pisano 周期【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki斐波那契数列The Fibonacci sequence是组合数学与数论中最基础也最重要的整数序列之一本指南围绕 OI Wiki 中 斐波那契数列 一页完整梳理其定义、卢卡斯数列、Binet 通项公式、矩阵与快速倍增计算、七大经典性质、基于齐肯多夫定理的斐波那契编码以及模意义下的周期性Pisano 周期与其完整证明。读完本文你将掌握从 $\Theta(n)$ 递推、$\Theta(\log n)$ 矩阵快速幂到常数更小的快速倍增法等多种计算手段并能理解与使用 Pisano 周期在模意义下处理超大下标 $n$ 的斐波那契数。斐波那契数列与卢卡斯数列的定义OI Wiki 中斐波那契数列的定义如下OEIS A000045$$ F_0 0,\quad F_1 1,\quad F_n F_{n-1} F_{n-2} $$该数列的前几项为$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots $$与之关系极为密切的是卢卡斯数列The Lucas sequenceOEIS A000032它使用相同的线性递推规律、不同的初值$$ L_0 2,\quad L_1 1,\quad L_n L_{n-1} L_{n-2} $$其前几项为$$ 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, \dots $$在 OI Wiki 中特别强调研究斐波那契数列时很多时候需要借助卢卡斯数列作为工具——两者的通项公式、递推矩阵乃至三角恒等式层面均高度同构这一点将在后文反复体现。通项公式解析解第 $n$ 个斐波那契数可以使用递推公式在 $\Theta(n)$ 时间内计算但存在更快速的方法其理论基础之一是解析解。斐波那契数列的 Binet 公式斐波那契数列有著名的通项公式Binets Formula$$ F_n \frac{\left(\frac{1 \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}} $$这一公式可以用归纳法直接证明通过生成函数参见 组合计数 相关章节推导通过解特征方程 $x^2x1$ 得到。一个实用观察是公式分子中的第二项 $\left(\frac{1 - \sqrt{5}}{2}\right)^n$ 的绝对值恒小于 $1$并且随 $n$ 以指数级速度衰减。因此公式可近似为“取最近整数”的形式$$ F_n \left[\frac{\left(\frac{1 \sqrt{5}}{2}\right)^n}{\sqrt{5}}\right] $$其中中括号表示取离它最近的整数。需要特别指出的是这两个公式在实数浮点计算中要求极高的精度因此在实践中很少直接使用。但正如 OI Wiki 所强调的——请不要忽视它结合模意义下的二次剩余用于处理 $\sqrt{5}$与逆元概念在 OI 中于模意义下使用该公式仍然有用。模意义下开平方的具体工具可参见 二次剩余。卢卡斯数列通项公式卢卡斯数列的通项公式与斐波那契高度对称$$ L_n \left(\frac{1 \sqrt{5}}{2}\right)^n \left(\frac{1 - \sqrt{5}}{2}\right)^n $$事实上两者被如下恒等式统一$$ \frac{L_n F_n\sqrt{5}}{2} \left(\frac{1 \sqrt{5}}{2}\right)^n $$也就是说$L_n$ 与 $F_n$ 恰好构成 $\left(\frac{1 \sqrt{5}}{2}\right)^n$ 在 $\mathbb{Q}(\sqrt{5})$ 中二项式展开、再按有理数部分与 $\sqrt{5}$ 系数部分合并后的分子系数。由此还可推出Pell 方程$$ x^2-5y^2-4 $$的全体正整数解恰好由$$ \frac{x_n y_n\sqrt{5}}{2} \frac{L_n F_n\sqrt{5}}{2} $$给出即 $x_nL_n,\ y_nF_n$。于是得到卢卡斯数与斐波那契数之间的一个重要恒等式$$ {L_n}^2-5{F_n}^2-4 $$快速计算斐波那契数列矩阵形式斐波那契数列的递推可以用矩阵乘法的形式表达$$ \begin{bmatrix}F_{n-1} F_{n} \cr\end{bmatrix} \begin{bmatrix}F_{n-2} F_{n-1} \cr\end{bmatrix} \begin{bmatrix}0 1 \cr 1 1 \cr\end{bmatrix} $$设 $P \begin{bmatrix}0 1 \cr 1 1 \cr\end{bmatrix}$反复迭代得到$$ \begin{bmatrix}F_n F_{n1} \cr\end{bmatrix} \begin{bmatrix}F_0 F_1 \cr\end{bmatrix} P^n $$于是可以用矩阵乘法在 $\Theta(\log n)$ 时间内计算斐波那契数列。这正是 OI Wiki 快速幂与矩阵快速幂 一章中“计算斐波那契数”一节的底层原理根据递推式 $F_n F_{n-1} F_{n-2}$ 构建 $2\times 2$ 的转移矩阵利用矩阵乘法结合律配合二进制拆分即可在 $\Theta(\log n)$ 内求出 $F_n$矩阵快速幂的完整实现参见 矩阵加速递推。此外前一节讲述的通项公式也可以通过矩阵对角化的技巧来得到该思路在本文 Pisano 周期证明的“利用扩域”一节中还会再次出现。快速倍增法基于矩阵递推还可以导出以下下标倍增等式$$ \begin{aligned} F_{2k} F_k (2 F_{k1} - F_{k}) \ F_{2k1} F_{k1}^2 F_{k}^2 \end{aligned} $$于是可以通过递归折半的方式快速计算两个相邻的斐波那契数常数因子比矩阵乘法更小。OI Wiki 给出的代码如下返回值是一个二元组 $(F_n, F_{n1})$pairint, int fib(int n) { if (n 0) return {0, 1}; auto p fib(n 1); int c p.first * (2 * p.second - p.first); int d p.first * p.first p.second * p.second; if (n 1) return {d, c d}; else return {c, d}; }该实现的时间复杂度为 $\Theta(\log n)$且每次递归只需要常数次乘法与加法避免了 $2\times 2$ 矩阵乘法中若干多余的运算因此在 OI 代码中常常是计算单个斐波那契数的首选。斐波那契数列的性质OI Wiki 列举了若干简单而重要、在竞赛中高频使用的性质卡西尼性质Cassinis identity$F_{n-1} F_{n1} - F_n^2 (-1)^n$。附加性质$F_{nk} F_k F_{n1} F_{k-1} F_n$。取上一条性质中 $k n$得到 $F_{2n} F_n (F_{n1} F_{n-1})$。由上一条性质可以归纳证明$\forall k\in \mathbb{N}$$F_n \mid F_{nk}$。上述性质可逆$\forall F_a \mid F_b$有 $a \mid b$。GCD 性质$(F_m, F_n) F_{(m, n)}$即斐波那契数的最大公约数等于下标最大公约数对应的斐波那契数。以斐波那契数列相邻两项作为欧几里得算法的输入会使该算法达到最坏复杂度拉梅定理。其中第 7 条性质与 最大公约数gcd 页面相互印证该页明确指出“假如我们试着用欧几里得算法去求斐波那契数列相邻两项的最大公约数会让该算法达到最坏复杂度”。这是分析欧几里得算法复杂度时的经典结论也是斐波那契数列与算法复杂度理论交汇的典型例子。斐波那契数列与卢卡斯数列的关系OI Wiki 指出一个极具启发性的观察关于卢卡斯数列与斐波那契数列的等式与三角函数公式具有很高的相似性。例如$$ \frac{L_n F_n\sqrt{5}}{2} \left(\frac{1 \sqrt{5}}{2}\right)^n $$与棣莫弗公式$$ \cos nx i\sin nx \left(\cos x i\sin x\right)^n $$形式几乎一致而$$ {L_n}^2-5{F_n}^2-4 $$则与$$ \cos^2 x \sin^2 x 1 $$相对应。因此可以直观地认为卢卡斯数列“像”余弦函数斐波那契数列“像”正弦函数。利用指数律 $\left(\frac{1 \sqrt{5}}{2}\right)^m\left(\frac{1 \sqrt{5}}{2}\right)^n \left(\frac{1 \sqrt{5}}{2}\right)^{mn}$可推出“两下标之和”的等式对应三角函数的和角公式$$ 2L_{mn}5F_mF_nL_mL_n $$$$ 2F_{mn}F_mL_nL_mF_n $$令 $mn$ 即得到“二倍下标”的等式对应倍角公式$$ L_{2n}{L_n}^2-2{\left(-1\right)}^n $$$$ F_{2n}F_nL_n $$其中 $F_{2n}F_nL_n$ 本身就是一种快速倍增下标的办法。同理还可以仿照三角函数的奇偶性、和差化积、积化和差、半角、万能代换等公式推理出更多有关卢卡斯数列与斐波那契数列的相应等式。斐波那契编码利用斐波那契数列可以为正整数编码。依据齐肯多夫定理Zeckendorfs theorem任何自然数 $n$ 都可以被唯一地表示成一些不相邻的斐波那契数之和$$ N F_{k_1} F_{k_2} \ldots F_{k_r} $$并且 $k_1 \ge k_2 2,\ k_2 \ge k_3 2,\ \ldots,\ k_r \ge 2$即不能使用两个相邻的斐波那契数。于是可以用 $d_0 d_1 d_2 \dots d_s 1$ 形式的编码表示一个正整数其中 $d_i1$ 表示 $F_{i2}$ 被使用。编码末位强制添加一个 $1$这样串中会出现两个相邻的 1用于标记编码的结束。几个编码例子如下OI Wiki 原例$$ \begin{aligned} 1 1 F_2 (11)_F \ 2 2 F_3 (011)_F \ 6 5 1 F_5 F_2 (10011)_F \ 8 8 F_6 (000011)_F \ 9 8 1 F_6 F_2 (100011)_F \ 19 13 5 1 F_7 F_5 F_2 (1001011)_F \end{aligned} $$给 $n$ 编码的过程可以用贪心算法解决从大到小枚举斐波那契数 $F_i$直到 $F_i \le n$。把 $n$ 减掉 $F_i$在编码的 $i-2$ 位置编码从左到右以 0 为起点放一个 1。如果 $n$ 为正回到步骤 1。最后在编码末位添加一个 1表示编码的结束位置。解码过程同理先删掉末位的 1对于编码中为 1 的位置 $i$从左到右以 0 为起点累加一个 $F_{i2}$ 到答案最终答案即为原数字。模意义下的周期性抽屉原理与周期性对于模 $m$ 意义下的斐波那契数列可以容易地使用抽屉原理证明其周期性。由于斐波那契数每一项都依赖于前两项需要用相邻斐波那契数组成的数对描述数列当前所处的状态。考虑模 $m$ 意义下前 $m^21$ 个斐波那契数对$$ (F_0,\ F_1),\ (F_1,\ F_2),\ \ldots,\ (F_{m^2},\ F_{m^2 1}) $$模 $m$ 的剩余系大小为 $m$因此至多只有 $m^2$ 种互不相同的数对。于是前 $m^21$ 个数对中必有两个相同从这两个相同数对起可以向后生成完全相同的斐波那契数列。故斐波那契数列模 $m$ 是周期性的且最小正周期不超过 $m^2$。Pisano 周期皮萨诺周期模 $m$ 意义下斐波那契数列的最小正周期被称为Pisano 周期皮萨诺周期OEIS A001175本文用 $\pi(m)$ 表示模 $m$ 的 Pisano 周期。这一观察可用于计算第 $n$ 项斐波那契数模 $m$ 的值如果 $n$ 非常大就需要先计算斐波那契数模 $m$ 的周期不要求一定是最小正周期。为此OI Wiki 给出了如下结论对于互素的模数 $m_1, m_2$有 $\pi(m_1m_2)\operatorname{lcm}(\pi(m_1),\pi(m_2))$。对于素数 $p$ 和正整数 $e$有 $\pi(p^{e})\mid p^{e-1}\pi(p)$。对于 $m2^e~(e\in\mathbf N_)$有 $\pi(m)3\cdot 2^{e-1}$。对于 $m5^e~(e\in\mathbf N_)$有 $\pi(m)4\cdot 5^e$。对于素数 $p\equiv\pm1\pmod{10}$有 $\pi(p)\mid(p-1)$对于素数 $p\equiv\pm3\pmod{10}$有 $\pi(p)\mid 2(p1)$。综合这些情形可以说明模 $m$ 的 Pisano 周期不超过 $6m$等号当且仅当 $m 2\times 5^e~(e\in\mathbf N_)$ 时取得。基于素因数分解的快速估算实现利用上述结论可以基于素因数分解算法得到如下快速计算 Pisano 周期或其倍数的方法。该参考代码位于 docs/math/code/combinatorics/fibonacci/pisano_estimate.cpp核心函数如下// Get a period of Fibonacci sequence mod m. // Not necessarily be the exact Pisano period. uint32_t calc_cycle_from_mod(uint32_t m) { uint32_t res 1; for (auto pe : factorize(m)) { auto p pe.first; auto e pe.second; uint64_t cur pow(p, e - 1); if (p 2) { cur * 3; } else if (p 5) { cur * 20; } else if (p % 5 1 || p % 5 4) { cur * p - 1; } else { cur * 2 * (p 1); } res lcm(res, cur); } return res; }该实现流程为先对 $m$ 做试除分解factorize复杂度 $O(\sqrt m)$对每个素因子幂 $p^e$ 按上述结论 3、4、5 求出 $\pi(p^e)$ 的一个可行倍数最后对所有素因子幂的周期取 $\operatorname{lcm}$。需要注意这样得到的周期可能只是 Pisano 周期的一个倍数因为结论 5 中的整除关系未必取到等号。要得到精确的 Pisano 周期可以进一步考察该周期的因数或者直接通过 BSGS 算法大步小步算法以 $O(\sqrt{m})$ 的时间复杂度计算。证明Pisano 周期不超过 $6m$OI Wiki 同时给出了上述结论的完整证明且明确指出利用该证明方法类似的结论可以推广到一般的二阶常系数线性齐次递推数列——尽管具体常数有所差异这些数列模 $m$ 的 Pisano 周期都是 $O(m)$ 的。证明分四步走第一步用中国剩余定理归约到素数幂模。利用 中国剩余定理可将讨论限制在素数幂模的情形。设 $m_1, m_2$ 互素斐波那契数列在模 $m_1$ 下的周期是 $\pi(m_1)$ 及其倍数在模 $m_2$ 下是 $\pi(m_2)$ 及其倍数因此在模 $m_1m_2$ 下的最小正周期恰为 $\pi(m_1)$ 与 $\pi(m_2)$ 的最小公倍数即结论 1。第二步把周期翻译成矩阵的阶。模 $m$ 下的 Pisano 周期其实是最小的正整数 $k$使得$$ A^k \begin{pmatrix} 11\10 \end{pmatrix}^k \equiv I \pmod{m} $$也就是说它是矩阵 $A$ 在模 $m$ 下严格来说在一般线性群 $GL_2(\mathbf Z_m)$ 中的阶。注意这里的矩阵 $A$ 与快速计算一节中使用的 $P$ 互为转置两者的幂次行为完全一致。第三步素数幂模的升幂论证。设 $k\pi(p^e)$则存在二阶方阵 $\Lambda$使得 $A^k p^e\Lambda I$ 成立。由二项式定理可知$$ A^{kp} (p^e\Lambda I)^p I \sum_{i1}^p\binom{p}{i}(p^e\Lambda)^i \equiv I\pmod{p^{e1}} $$因此由阶的性质有 $\pi(p^{e1})\mid kp p\pi(p^e)$。对 $e$ 归纳即可得 $\pi(p^e)\mid p^{e-1}\pi(p)$ 恒成立结论 2而 $p2$ 与 $p5$ 的具体值结论 3、4可单独验证。第四步素数模的两种证明方式。利用通项公式将 Binet 公式$$ F_n \dfrac{1}{\sqrt{5}}\left(\dfrac{1\sqrt{5}}{2}\right)^n - \dfrac{1}{\sqrt{5}}\left(\dfrac{1-\sqrt{5}}{2}\right)^n $$用二项式定理展开并消去根式项得到$$ F_n \dfrac{1}{2^{n-1}}\sum_{i0}^{\lfloor(n-1)/2\rfloor}\binom{n}{2i1}5^i $$对于 $p2$该表达式无法直接取模但可直接验证 $\pi(2)3$对于 $p5$有 $F_n\equiv n\cdot 3^{n-1}\pmod{p}$可直接验证 $\pi(5)20$对于 $p\equiv 1,4\pmod{5}$即 $p\equiv\pm1\pmod{10}$由 Lucas 定理$0kp$ 时 $\binom{p}{k}\equiv0\pmod p$、Fermat 小定理$2^{p-1}\equiv5^{p-1}\equiv1\pmod p$以及二次互反律$p\equiv1,4\pmod5$ 时 $5$ 是模 $p$ 的二次剩余故 $5^{(p-1)/2}\equiv1\pmod p$可推出 $F_p\equiv F_{p1}\equiv1\pmod p$即 $(F_p,F_{p1})\equiv(F_1,F_2)\pmod p$于是 $p-1$ 是模 $p$ 的一个周期$\pi(p)\mid(p-1)$对于 $p\equiv 2,3\pmod{5}$即 $p\equiv\pm3\pmod{10}$同理利用二次互反律可知 $5$ 是模 $p$ 的二次非剩余$5^{(p-1)/2}\equiv-1\pmod p$结合 Lucas 定理与 $\binom{2p}{p}\equiv2\pmod p$ 等结论可推出 $F_{2p}\equiv F_{2p1}\equiv-1\pmod p$即 $(F_{2p},F_{2p1})\equiv(F_{-2},F_{-1})\pmod p$故 $2(p1)$ 是模 $p$ 的一个周期$\pi(p)\mid2(p1)$。该方法的局限在于高度依赖斐波那契数列的通项公式较难直接推广到一般情形。利用扩域直接计算矩阵 $A\begin{pmatrix}11\10\end{pmatrix}$ 的阶。其特征多项式为 $f(x)x^2-x-1$判别式 $\Delta5$模 $p5$ 时 $\Delta\equiv0\pmod5$矩阵 $A$ 有两个相同特征值 $\lambda3$ 且不可对角化需单独计算模 $p\equiv1,4\pmod5$ 时由二次互反律知 $5$ 是模 $p$ 的二次剩余$A$ 在域 $\mathbf F_p$ 内有两个相异特征值其阶为 $\operatorname{lcm}(\operatorname{ord}(\lambda_1),\operatorname{ord}(\lambda_2))$整除 $|\mathbf F_p^\times|p-1$模 $p\equiv2,3\pmod5$ 时$5$ 是模 $p$ 的二次非剩余$A$ 在 $\mathbf F_p$ 内没有特征值只有在扩域 $\mathbf F_p[\sqrt{5}]$ 内才有两个相异特征值。由于 Frobenius 自同态 $x\mapsto x^p$ 交换两根$\lambda_2\lambda_1^p$故 $\lambda_1^{p1}\lambda_2^{p1}\lambda_1\lambda_2-1$进而 $\lambda_1^{2(p1)}\lambda_2^{2(p1)}1$矩阵 $A$ 的阶整除 $2(p1)$。汇总上界。综合以上所有情形$\pi(2^e)\dfrac{3}{2}\cdot 2^e,\ \dfrac{1}{4}\pi(5^e)5^e$$p\equiv\pm1\pmod{10}$ 时$\pi(p^e)\mid(p-1)p^{e-1}$故 $\pi(p^e)\le p^e$$p\equiv\pm3\pmod{10}$ 时$\dfrac{1}{4}\pi(p^e)\mid\dfrac{p1}{2}p^{e-1}$故 $\dfrac{1}{4}\pi(p^e)\le p^e$。再利用结论 1对一般的模数 $m\prod_i p_i^{e_i}$ 有$$ \begin{aligned} \pi(m)\operatorname{lcm}{\pi(p_i^{e_i}):p_i\in\mathbf P} \ \le \operatorname{lcm}{\pi(p_i^{e_i}):p_i2\text{ or }p_i\equiv\pm1~(\operatorname{mod}{10})}\ \quad \cdot 4\cdot\operatorname{lcm}{\pi(p_i^{e_i})/4:p_i5\text{ or }p_i\equiv\pm3~(\operatorname{mod}{10})}\ \le \prod{\pi(p_i^{e_i}):p_i2\text{ or }p_i\equiv\pm1~(\operatorname{mod}{10})}\ \quad \cdot 4\cdot\prod{\pi(p_i^{e_i})/4:p_i5\text{ or }p_i\equiv\pm3~(\operatorname{mod}{10})}\ \le \dfrac{3}{2}\cdot\prod{p_i^{e_i}:p_i2\text{ or }p_i\equiv\pm1~(\operatorname{mod}{10})}\ \quad \cdot 4\cdot\prod{p_i^{e_i}:p_i5\text{ or }p_i\equiv\pm3~(\operatorname{mod}{10})}\ 6m \end{aligned} $$这就严格证明了斐波那契数列模 $m$ 的 Pisano 周期总是不超过 $6m$且等号当且仅当 $m2\cdot 5^e$ 时取得。实战应用与进一步学习Pisano 周期在实践中最重要的用途是当 $n$ 极大例如 $n\approx 10^{18}$ 甚至更大而需要计算 $F_n \bmod m$ 时先求出模 $m$ 的一个周期 $T$再令 $n n \bmod T$用快速倍增法或矩阵快速幂计算 $F_{n}\bmod m$ 即可从而把问题规模从 $n$ 缩小到周期量级。结合本文给出的calc_cycle_from_mod实现完整可运行代码与精确周期获取手段BSGS见 离散对数即可在模意义下高效处理超大规模的斐波那契数查询。OI Wiki 为本文内容提供了成体系的支撑材料可继续深入阅读快速幂与矩阵快速幂矩阵快速幂计算斐波那契数的方法论基础矩阵与矩阵加速递推$2\times2$ 转移矩阵的工程实现最大公约数斐波那契相邻项使欧几里得算法达到最坏复杂度的应用二次剩余 与 二次互反律模意义下处理 $\sqrt{5}$ 与素数模周期证明的关键工具中国剩余定理、Lucas 定理、Fermat 小定理、原根与幂的循环结构Pisano 周期证明中各步骤的数论基础群论与阶、域与扩域、特征多项式将周期问题转化为矩阵阶问题的代数语言。此外原页面还推荐了若干经典练习如欧几里得算法重访、斐波那契求和、判断是否为斐波那契数、偶斐波那契数求和、超大模数下的 $F_n$ 计算等可作为巩固上述概念的实战训练。参考说明本页内容主要译自经典算法资料《Числа Фибоначчи》Fibonacci Numbers及其英文翻译版并在 OI Wiki 的框架下结合中文竞赛语境进行了改写与扩充文中公式、代码与结论均可在 docs/math/combinatorics/fibonacci.md 及 docs/math/code/combinatorics/fibonacci/pisano_estimate.cpp 中直接核对。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考