OI Wiki 斐波那契数列全解：通项公式、快速计算、斐波那契编码与 Pisano 周期-育师

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 sequence，OEIS 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 公式

斐波那契数列有著名的通项公式（Binet's Formula）：

$$ F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}} $$

这一公式可以：

用归纳法直接证明；
通过生成函数（参见组合计数相关章节）推导；
通过解特征方程 $x^2=x+1$ 得到。

一个实用观察是：公式分子中的第二项 $\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_n=L_n,\ y_n=F_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_{n+1} \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_{k+1} - F_{k}) \ F_{2k+1} &= F_{k+1}^2 + F_{k}^2 \end{aligned} $$

于是可以通过递归折半的方式快速计算两个相邻的斐波那契数（常数因子比矩阵乘法更小）。OI Wiki 给出的代码如下，返回值是一个二元组 $(F_n, F_{n+1})$：

pair<int, 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 列举了若干简单而重要、在竞赛中高频使用的性质：

卡西尼性质（Cassini's identity）：$F_{n-1} F_{n+1} - F_n^2 = (-1)^n$。
附加性质：$F_{n+k} = F_k F_{n+1} + F_{k-1} F_n$。
取上一条性质中 $k = n$，得到 $F_{2n} = F_n (F_{n+1} + 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)^{m+n}$，可推出“两下标之和”的等式（对应三角函数的和角公式）：

$$ 2L_{m+n}=5F_mF_n+L_mL_n $$

$$ 2F_{m+n}=F_mL_n+L_mF_n $$

令 $m=n$ 即得到“二倍下标”的等式（对应倍角公式）：

$$ L_{2n}={L_n}^2-2{\left(-1\right)}^n $$

$$ F_{2n}=F_nL_n $$

其中 $F_{2n}=F_nL_n$ 本身就是一种快速倍增下标的办法。同理，还可以仿照三角函数的奇偶性、和差化积、积化和差、半角、万能代换等公式，推理出更多有关卢卡斯数列与斐波那契数列的相应等式。

斐波那契编码

利用斐波那契数列可以为正整数编码。依据齐肯多夫定理（Zeckendorf's 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_i=1$ 表示 $F_{i+2}$ 被使用。编码末位强制添加一个 $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_{i+2}$ 到答案，最终答案即为原数字。

模意义下的周期性

抽屉原理与周期性

对于模 $m$ 意义下的斐波那契数列，可以容易地使用抽屉原理证明其周期性。由于斐波那契数每一项都依赖于前两项，需要用相邻斐波那契数组成的数对描述数列当前所处的状态。考虑模 $m$ 意义下前 $m^2+1$ 个斐波那契数对：

$$ (F_0,\ F_1),\ (F_1,\ F_2),\ \ldots,\ (F_{m^2},\ F_{m^2 + 1}) $$

模 $m$ 的剩余系大小为 $m$，因此至多只有 $m^2$ 种互不相同的数对。于是前 $m^2+1$ 个数对中必有两个相同，从这两个相同数对起可以向后生成完全相同的斐波那契数列。故斐波那契数列模 $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)$。
对于 $m=2^e~(e\in\mathbf N_+)$，有 $\pi(m)=3\cdot 2^{e-1}$。
对于 $m=5^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(p+1)$。

综合这些情形可以说明：模 $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} 1&1\1&0 \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_{i=1}^p\binom{p}{i}(p^e\Lambda)^i \equiv I\pmod{p^{e+1}} $$

因此，由阶的性质，有 $\pi(p^{e+1})\mid kp = p\pi(p^e)$。对 $e$ 归纳即可得 $\pi(p^e)\mid p^{e-1}\pi(p)$ 恒成立（结论 2），而 $p=2$ 与 $p=5$ 的具体值（结论 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_{i=0}^{\lfloor(n-1)/2\rfloor}\binom{n}{2i+1}5^i $$
- 对于 $p=2$，该表达式无法直接取模，但可直接验证 $\pi(2)=3$；
- 对于 $p=5$，有 $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 定理（$0<k<p$ 时 $\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_{p+1}\equiv1\pmod p$，即 $(F_p,F_{p+1})\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_{2p+1}\equiv-1\pmod p$，即 $(F_{2p},F_{2p+1})\equiv(F_{-2},F_{-1})\pmod p$，故 $2(p+1)$ 是模 $p$ 的一个周期，$\pi(p)\mid2(p+1)$。
该方法的局限在于高度依赖斐波那契数列的通项公式，较难直接推广到一般情形。
利用扩域：直接计算矩阵 $A=\begin{pmatrix}1&1\1&0\end{pmatrix}$ 的阶。其特征多项式为 $f(x)=x^2-x-1$，判别式 $\Delta=5$：
- 模 $p=5$ 时 $\Delta\equiv0\pmod5$，矩阵 $A$ 有两个相同特征值 $\lambda=3$ 且不可对角化，需单独计算；
- 模 $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^{p+1}=\lambda_2^{p+1}=\lambda_1\lambda_2=-1$，进而 $\lambda_1^{2(p+1)}=\lambda_2^{2(p+1)}=1$，矩阵 $A$ 的阶整除 $2(p+1)$。

汇总上界。综合以上所有情形：

$\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{p+1}{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_i=2\text{ or }p_i\equiv\pm1~(\operatorname{mod}{10})}\ &\quad \cdot 4\cdot\operatorname{lcm}{\pi(p_i^{e_i})/4:p_i=5\text{ or }p_i\equiv\pm3~(\operatorname{mod}{10})}\ &\le \prod{\pi(p_i^{e_i}):p_i=2\text{ or }p_i\equiv\pm1~(\operatorname{mod}{10})}\ &\quad \cdot 4\cdot\prod{\pi(p_i^{e_i})/4:p_i=5\text{ or }p_i\equiv\pm3~(\operatorname{mod}{10})}\ &\le \dfrac{3}{2}\cdot\prod{p_i^{e_i}:p_i=2\text{ or }p_i\equiv\pm1~(\operatorname{mod}{10})}\ &\quad \cdot 4\cdot\prod{p_i^{e_i}:p_i=5\text{ or }p_i\equiv\pm3~(\operatorname{mod}{10})}\ &= 6m \end{aligned} $$

这就严格证明了斐波那契数列模 $m$ 的 Pisano 周期总是不超过 $6m$，且等号当且仅当 $m=2\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），仅供参考