

斐波那契数列

斐波那契数列（The Fibonacci sequence，OEIS A000045）的定义如下：

该数列的前几项如下：

卢卡斯数列¶

卢卡斯数列（The Lucas sequence，OEIS A000032）的定义如下：

该数列的前几项如下：

研究斐波那契数列，很多时候需要借助卢卡斯数列为工具。

斐波那契数列通项公式¶

第个斐波那契数可以在的时间内使用递推公式计算。但我们仍有更快速的方法计算。

解析解¶

解析解即公式解。我们有斐波那契数列的通项公式（Binet's Formula）：

这个公式可以很容易地用归纳法证明，当然也可以通过生成函数的概念推导，或者解一个方程得到。

当然你可能发现，这个公式分子的第二项总是小于，并且它以指数级的速度减小。因此我们可以把这个公式写成

这里的中括号表示取离它最近的整数。

这两个公式在计算的时侯要求极高的精确度，因此在实践中很少用到。但是请不要忽视！结合模意义下二次剩余和逆元的概念，在 OI 中使用这个公式仍是有用的。

卢卡斯数列通项公式¶

我们有卢卡斯数列的通项公式：

与斐波那契数列非常相似。事实上有：

也就是说，和恰好构成二项式展开再合并同类项后的分子系数。也就是说，Pell 方程

的全体解，恰好是

恰好是卢卡斯数列和斐波那契数列。因此有

矩阵形式¶

斐波那契数列的递推可以用矩阵乘法的形式表达：

设，我们得到

于是我们可以用矩阵乘法在的时间内计算斐波那契数列。此外，前一节讲述的公式也可通过矩阵对角化的技巧来得到。

快速倍增法¶

使用上面的方法我们可以得到以下等式：

于是可以通过这样的方法快速计算两个相邻的斐波那契数（常数比矩乘小）。代码如下，返回值是一个二元组。

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};
}

性质¶

斐波那契数列拥有许多有趣的性质，这里列举出一部分简单的性质：

卡西尼性质（Cassini's identity）：。
附加性质：。
取上一条性质中，我们得到。
由上一条性质可以归纳证明，。
上述性质可逆，即。
GCD 性质：。
以斐波那契数列相邻两项作为输入会使欧几里德算法达到最坏复杂度（具体参见维基 - 拉梅）。

斐波那契数列与卢卡斯数列的关系¶

不难发现，关于卢卡斯数列与斐波那契数列的等式，与三角函数公式具有很高的相似性。比如：

与

很像。以及

与

很像。因此，卢卡斯数列与余弦函数很像，而斐波那契数列与正弦函数很像。比如，根据

可以得到两下标之和的等式：

于是推论就有二倍下标的等式：

这也是一种快速倍增下标的办法。同样地，也可以仿照三角函数的公式，比如奇偶性、和差化积、积化和差、半角、万能代换等等，推理出更多有关卢卡斯数列与斐波那契数列的相应等式。

斐波那契编码¶

我们可以利用斐波那契数列为正整数编码。根据齐肯多夫定理，任何自然数可以被唯一地表示成一些斐波那契数的和：

并且（即不能使用两个相邻的斐波那契数）

于是我们可以用的编码表示一个正整数，其中则表示被使用。编码末位我们强制给它加一个 1（这样会出现两个相邻的 1），表示这一串编码结束。举几个例子：

给编码的过程可以使用贪心算法解决：

从大到小枚举斐波那契数，直到。
把减掉，在编码的的位置上放一个 1（编码从左到右以 0 为起点）。
如果为正，回到步骤 1。
最后在编码末位添加一个 1，表示编码的结束位置。

解码过程同理，先删掉末位的 1，对于编码为 1 的位置（编码从左到右以 0 为起点），累加一个到答案。最后的答案就是原数字。

模意义下周期性¶

考虑模意义下的斐波那契数列，可以容易地使用抽屉原理证明，该数列是有周期性的。考虑模意义下前个斐波那契数对（两个相邻数配对）：

的剩余系大小为，意味着在前个数对中必有两个相同的数对，于是这两个数对可以往后生成相同的斐波那契数列，那么他们就是周期性的。

皮萨诺周期¶

模意义下斐波那契数列的最小正周期被称为皮萨诺周期（Pisano periods,OEIS A001175）。

皮萨诺周期总是不超过，且只有在满足的形式时才取到等号。

当需要计算第项斐波那契数模的值的时候，如果非常大，就需要计算斐波那契数模的周期。当然，只需要计算周期，不一定是最小正周期。

容易验证，斐波那契数模的最小正周期是，模的最小正周期是。

显然，如果与互素，的皮萨诺周期就是的皮萨诺周期与的皮萨诺周期的最小公倍数。

计算周期还需要以下结论：

结论 1：对于奇素数，是斐波那契数模的周期。即，奇素数的皮萨诺周期整除。

证明：

此时。

由二项式展开：

因为和两项都同余于，与和一致，所以是周期。

结论 2：对于奇素数，是斐波那契数模的周期。即，奇素数的皮萨诺周期整除。

证明：

此时。

由二项式展开：

模之后，在式中，只有项留了下来；在式中，有、、，三项留了下来。

于是和两项与和一致，所以是周期。

结论 3：对于素数，是斐波那契数模的周期，等价于是斐波那契数模的周期。特别地，是模的皮萨诺周期，等价于是模的皮萨诺周期。

证明：

这里的证明需要把看作一个整体。

由于：

因此：

因为反方向也可以推导，所以是斐波那契数模的周期，等价于：

当是奇素数时，根据模奇素数的升幂定理，有：

当是时，根据模的升幂定理，有：

代入为和，为和，上述条件也就等价于：

因此也等价于是斐波那契数模的周期。

因为周期等价，所以最小正周期也等价。

三个结论证完。据此可以写出代码：

struct prime {
  unsigned long long p;
  int times;
};

struct prime pp[2048];
int pptop;

unsigned long long get_cycle_from_mod(
    unsigned long long mod)  // 这里求解的只是周期，不一定是最小正周期
{
  pptop = 0;
  srand(time(0));
  while (n != 1) {
    __int128_t factor = (__int128_t)10000000000 * 10000000000;
    min_factor(mod, &factor);  // 计算最小素因数
    struct prime temp;
    temp.p = factor;
    for (temp.times = 0; mod % factor == 0; temp.times++) {
      mod /= factor;
    }
    pp[pptop] = temp;
    pptop++;
  }
  unsigned long long m = 1;
  for (int i = 0; i < pptop; ++i) {
    int g;
    if (pp[i].p == 2) {
      g = 3;
    } else if (pp[i].p == 5) {
      g = 20;
    } else if (pp[i].p % 5 == 1 || pp[i].p % 5 == 4) {
      g = pp[i].p - 1;
    } else {
      g = (pp[i].p + 1) << 1;
    }
    m = lcm(m, g * qpow(pp[i].p, pp[i].times - 1));
  }
  return m;
}

习题¶

SPOJ - Euclid Algorithm Revisited
SPOJ - Fibonacci Sum
HackerRank - Is Fibo
Project Euler - Even Fibonacci numbers
洛谷 P4000 斐波那契数列

本页面主要译自博文 Числа Фибоначчи 与其英文翻译版 Fibonacci Numbers。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用