斐波那契数列学习笔记

#1 定义

斐波那契数列

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

F_{0} = 0, F_{1} = 1, 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, L_{1} = 1, L_{n} = L_{n - 1} + L_{n - 2}

该数列的前几项如下：

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, \dots

NOTE

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

#2 斐波那契数列通项公式

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

2.1 解析解

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

F_{n} = \frac{{(\frac{1 + \sqrt{5}}{2})}^{n} - {(\frac{1 - \sqrt{5}}{2})}^{n}}{\sqrt{5}}

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

简化

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

F_{n} = [\frac{{(\frac{1 + \sqrt{5}}{2})}^{n}}{\sqrt{5}}]

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

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

2.2 矩阵形式

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

[\begin{matrix} F_{n - 1} & F_{n} \end{matrix}] = [\begin{matrix} F_{n - 2} & F_{n - 1} \end{matrix}] [\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}]

设 $P = [\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}]$ ，我们得到

[\begin{matrix} F_{n} & F_{n + 1} \end{matrix}] = [\begin{matrix} F_{0} & F_{1} \end{matrix}] P^{n}

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

快速倍增法

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

\begin{aligned} F_{2 k} & = F_{k} (2 F_{k + 1} - F_{k}) \\ F_{2 k + 1} & = F_{k + 1}^{2} + F_{k}^{2} \end{aligned}

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

cpp

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

#3 模意义下周期性

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

(F_{1}, F_{2}), (F_{2}, F_{3}), \dots, (F_{p^{2} + 1}, F_{p^{2} + 2})

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

3.1 皮萨诺周期

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

皮萨诺周期总是不超过 $6 m$ ，且只有在满足 $m = 2 \times 5^{k}$ 的形式时才取到等号。

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

容易验证，斐波那契数模 $2$ 的最小正周期是 $3$ ，模 $5$ 的最小正周期是 $20$ 。

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

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

结论 1：对于奇素数 $p \equiv 1, 4 (\mod 5)$ ， $p - 1$ 是斐波那契数模 $p$ 的周期。即，奇素数 $p$ 的皮萨诺周期整除 $p - 1$ 。

证明：

此时 $5^{\frac{p - 1}{2}} \equiv 1 (\mod p)$ 。

由二项式展开：

F_{p} = \frac{2}{2^{p} \sqrt{5}} ((\binom{p}{1}) \sqrt{5} + (\binom{p}{3}) {\sqrt{5}}^{3} + \dots + (\binom{p}{p}) {\sqrt{5}}^{p}) \equiv {\sqrt{5}}^{p - 1} \equiv 1 (\mod p)

F_{p + 1} = \frac{2}{2^{p + 1} \sqrt{5}} ((\binom{p + 1}{1}) \sqrt{5} + (\binom{p + 1}{3}) {\sqrt{5}}^{3} + \dots + (\binom{p + 1}{p}) {\sqrt{5}}^{p}) \equiv \frac{1}{2} (1 + {\sqrt{5}}^{p - 1}) \equiv 1 (\mod p)

因为 $F_{p}$ 和 $F_{p + 1}$ 两项都同余于 $1$ ，与 $F_{1}$ 和 $F_{2}$ 一致，所以 $p - 1$ 是周期。

结论 2：对于奇素数 $p \equiv 2, 3 (\mod 5)$ ， $2 p + 2$ 是斐波那契数模 $p$ 的周期。即，奇素数 $p$ 的皮萨诺周期整除 $2 p + 2$ 。

证明：

此时 $5^{\frac{p - 1}{2}} \equiv - 1 (\mod p)$ 。

由二项式展开：

F_{2 p} = \frac{2}{2^{2 p} \sqrt{5}} ((\binom{2 p}{1}) \sqrt{5} + (\binom{2 p}{3}) {\sqrt{5}}^{3} + \dots + (\binom{2 p}{2 p - 1}) {\sqrt{5}}^{2 p - 1})

F_{2 p + 1} = \frac{2}{2^{2 p + 1} \sqrt{5}} ((\binom{2 p + 1}{1}) \sqrt{5} + (\binom{2 p + 1}{3}) {\sqrt{5}}^{3} + \dots + (\binom{2 p + 1}{2 p + 1}) {\sqrt{5}}^{2 p + 1})

模 $p$ 之后，在 $F_{2 p}$ 式中，只有 $(\binom{2 p}{p}) \equiv 2 (\mod p)$ 项留了下来；在 $F_{2 p + 1}$ 式中，有 $(\binom{2 p + 1}{1}) \equiv 1 (\mod p)$ 、 $(\binom{2 p + 1}{p}) \equiv 2 (\mod p)$ 、 $(\binom{2 p + 1}{2 p + 1}) \equiv 1 (\mod p)$ ，三项留了下来。

F_{2 p} \equiv \frac{1}{2} (\binom{2 p}{p}) {\sqrt{5}}^{p - 1} \equiv - 1 (\mod p)

F_{2 p + 1} \equiv \frac{1}{4} ((\binom{2 p + 1}{1}) + (\binom{2 p + 1}{p}) {\sqrt{5}}^{p - 1} + (\binom{2 p + 1}{2 p + 1}) {\sqrt{5}}^{2 p}) \equiv \frac{1}{4} (1 - 2 + 5) \equiv 1 (\mod p)

于是 $F_{2 p}$ 和 $F_{2 p + 1}$ 两项与 $F_{- 2}$ 和 $F_{- 1}$ 一致，所以 $2 p + 2$ 是周期。

结论 3：对于素数 $p$ ， $M$ 是斐波那契数模 $p^{k - 1}$ 的周期，等价于 $M p$ 是斐波那契数模 $p^{k}$ 的周期。特别地， $M$ 是模 $p^{k - 1}$ 的皮萨诺周期，等价于 $M p$ 是模 $p^{k}$ 的皮萨诺周期。

证明：

这里的证明需要把 $\frac{1 + \sqrt{5}}{2}$ 看作一个整体。

由于：

F_{M} = \frac{1}{\sqrt{5}} ({(\frac{1 + \sqrt{5}}{2})}^{M} - {(\frac{1 - \sqrt{5}}{2})}^{M}) \equiv 0 (\mod p^{k - 1})

F_{M + 1} = \frac{1}{\sqrt{5}} ({(\frac{1 + \sqrt{5}}{2})}^{M + 1} - {(\frac{1 - \sqrt{5}}{2})}^{M + 1}) \equiv 1 (\mod p^{k - 1})

因此：

{(\frac{1 + \sqrt{5}}{2})}^{M} \equiv {(\frac{1 - \sqrt{5}}{2})}^{M} (\mod p^{k - 1})

1 \equiv \frac{1}{\sqrt{5}} {(\frac{1 + \sqrt{5}}{2})}^{M} ((\frac{1 + \sqrt{5}}{2}) - (\frac{1 - \sqrt{5}}{2})) = {(\frac{1 + \sqrt{5}}{2})}^{M} (\mod p^{k - 1})

因为反方向也可以推导，所以 $M$ 是斐波那契数模 $p^{k - 1}$ 的周期，等价于：

{(\frac{1 + \sqrt{5}}{2})}^{M} \equiv {(\frac{1 - \sqrt{5}}{2})}^{M} \equiv 1 (\mod p^{k - 1})

当 $p$ 是奇素数时，由升幂引理，有：

v_{p} (a^{t} - 1) = v_{p} (a - 1) + v_{p} (t)

当 $p = 2$ 时，由升幂引理，有：

v_{2} (a^{t} - 1) = v_{2} (a - 1) + v_{2} (a + 1) + v_{2} (t) - 1

代入 $a$ 为 $(\frac{1 + \sqrt{5}}{2})$ 和 $(\frac{1 - \sqrt{5}}{2})$ ， $t$ 为 $M$ 和 $M p$ ，上述条件也就等价于：

{(\frac{1 + \sqrt{5}}{2})}^{M p} \equiv {(\frac{1 - \sqrt{5}}{2})}^{M p} \equiv 1 (\mod p^{k})

因此也等价于 $M p$ 是斐波那契数模 $p^{k}$ 的周期。

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

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

cpp

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(nullptr));
    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;
}

斐波那契数列 学习笔记 ​

#1 定义 ​