斐波那契循环节小记

· · 算法·理论

线性递推数列相关

设有一个 k 阶线性递推数列 f_i = \sum\limits_{j = 1}^{k} c_j f_{i - j}

定义其特征方程为 x^k = \sum\limits_{j = 1}^{k} c_j x^{k - j}

设在复数域中该方程的解为 \lambda_1, \lambda_2, \cdots, \lambda_k，则 f_n = \lambda_i^n 是该数列的一个特解。

由数学归纳法与特征方程定义易证 \lambda_1^n, \lambda_2^n, \cdots, \lambda_k^n 的任意线性组合与 f_n 的解一一对应。

若给出了 f_0 \sim f_{k - 1} 的值，考虑关于 k 维向量 \alpha 的方程组

\begin{cases} \alpha_1 + \alpha_2 + \cdots + \alpha_k = f_0 \\ \alpha_1 \lambda_1 + \alpha_2 \lambda_2 + \cdots + \alpha_k \lambda_k = f_1 \\ \vdots \\ \alpha_1 \lambda_1^{k - 1} + \alpha_2 \lambda_2^{k - 1} + \cdots + \alpha_k \lambda_k^{k - 1} = f_{k - 1} \end{cases}

则其系数矩阵为范德蒙德矩阵，其行列式为

\begin{vmatrix} 1 & 1 & \cdots & 1 \\ \lambda_1^1 & \lambda_2^1 & \cdots & \lambda_k^1 \\ \vdots & \vdots & \ddots & \vdots \\ \lambda_1^{k - 1} & \lambda_2^{k - 1} & \cdots & \lambda_k^{k - 1} \end{vmatrix}

当 \lambda_1 \sim \lambda_k 互不相等时，该行列式值非零，即上述方程组有唯一解，即递推数列通项公式为 f_n = \sum\limits_{i = 1}^k \alpha_i \lambda_i^n。

斐波那契循环节

斐波那契序列递推式：f_i = \begin{cases}i & i < 2 \\ f_{i - 1} + f_{i - 2} & i \ge 2 \end{cases}

对于任意模数 m，考虑求出最小的 t 满足 f_t \equiv f_0 \pmod m 且 f_{t + 1} \equiv f_1 \pmod m

记 \phi 与 \hat{\phi} 为斐波那契数列的特征方程 x^2 - x - 1 = 0 的两根，即 \phi = \frac{1 + \sqrt{5}}{2}, \hat{\phi} = \frac{1 - \sqrt{5}}{2}，有 f_n = \dfrac{\phi^n - \hat{\phi}^n}{\sqrt{5}}

首先考虑将 m 拆分成 \prod\limits_i p_i^{k_i}，对每个 p^k 求解后 CRT 合并。

现在考虑对于 m = p^k 求解

引理 1：a \equiv 1 \pmod p \Rightarrow a^{p^k} \equiv 1 \pmod {p^{k + 1}}

证明：考虑数学归纳法，设已知 a^{p^{k - 1}} \equiv 1 \pmod {p^k}。

则 a^{p^{k - 1}} = t p^k + 1。

则 a^{p^k} = (a^{p^{k - 1}})^p = (t p^k + 1)^p = 1 + \sum\limits_{i = 1}^p {\dbinom{p}{i} (t p^k)^i} \equiv 1 \pmod {p^{k + 1}}

设 m = p^k 时循环节为 T，m = p 时循环节为 t。

则满足 f_t = \dfrac{\phi^t - \hat{\phi}^t}{\sqrt{5}} \equiv 0 \pmod p，则 \phi^t \equiv \hat{\phi}^t \pmod p

又有 f_{t + 1} = \dfrac{\phi^{t + 1} - \hat{\phi}^{t + 1}}{\sqrt{5}} \equiv \phi^t \times \dfrac{\phi - \hat{\phi}}{\sqrt{5}} = \phi^t f_1 \equiv 1 \pmod p，即 \phi^t \equiv 1 \pmod p。

由引理 1 得 \phi^{t p^{k - 1}} \equiv \hat{\phi}^{t p^{k - 1}} \equiv 1 \pmod {p^k}，此时 T \le tp^{k - 1}，所以只需考虑 m = p 时的情况。

首先有 t = \begin{cases}2 & p = 2 \\ 8 & p = 3 \\ 20 & p = 5 & \end{cases}

剩余 p > 5 的情况分两类：

则对于 m = p^k 时 t 的取值在 O(m) 级别，而 CRT 合并后的 t 为原所有 t 的 \operatorname{lcm}，所以仍然是 O(m) 级别。具体地，t \le 6m（暂时不会证，留坑），可以 O(m) 求解。

例题

P7325 [WC2021] 斐波那契

记斐波那契数列为 f。

则有 F_i = a f_{i - 1} + b f_i，要求即为最小的 t 满足 a f_{t - 1} + b f_t \equiv 0 \pmod m。

这个式子不太优美，考虑令 b \leftarrow (m - b) \bmod m，则上式为 a f_{t - 1} \equiv b f_t \pmod m。

令 a, b, m 同除以 \gcd(a, b, m)，记 a' = \dfrac{a}{\gcd(a, b, m)}, b' = \dfrac{b}{\gcd(a, b, m)}, m' = \dfrac{m}{\gcd(a, b, m)}

则有 a' f_{t - 1} \equiv b' f_t \pmod {m'}。

引理 2：a \mid m \Rightarrow \forall a \mid (x \bmod m), a \mid x

证明显然。

考虑有

\begin{cases} \gcd(a', m') \mid (a' f_{t - 1} \bmod m') \\ \gcd(f_{t - 1}, m') \mid (a' f_{t - 1} \bmod m') \\ \gcd(b', m') \mid (b' f_t \bmod m') \\ \gcd(f_t, m') \mid (b' f_t \bmod m') \end{cases}

由 a' f_{t - 1} \equiv b' f_t \pmod {m'} 得

\begin{cases} \gcd(a', m') \mid (b' f_t \bmod m') \\ \gcd(f_{t - 1}, m') \mid (b' f_t \bmod m') \\ \gcd(b', m') \mid (a' f_{t - 1} \bmod m') \\ \gcd(f_t, m') \mid (a' f_{t - 1} \bmod m') \end{cases} \Longrightarrow \begin{cases} \gcd(a', m') \mid b' f_t \\ \gcd(f_{t - 1}, m') \mid b' f_t \\ \gcd(b', m') \mid a' f_{t - 1} \\ \gcd(f_t, m') \mid a' f_{t - 1} \end{cases}

有 \gcd(a', b', m') = 1, \gcd(f_t, f_{t - 1}) = 1，所以

\begin{cases} \gcd(a', m') \mid f_t \\ \gcd(f_{t - 1}, m') \mid b' \\ \gcd(b', m') \mid f_{t - 1} \\ \gcd(f_t, m') \mid a' \end{cases}

提取其中两式得

\begin{cases} \gcd(a', m') \mid f_t \\ \gcd(f_t, m') \mid a' \end{cases} \Longrightarrow \begin{cases} \gcd(a', m') \mid \gcd(f_t, m') \\ \gcd(f_t, m') \mid \gcd(a', m') \end{cases} \Longrightarrow \gcd(a', m') = \gcd(f_t, m')

同理可得 \gcd(b', m') = \gcd(f_{t - 1}, m')

则有 a' f_{t - 1} \equiv b' f_t \pmod {m'} \Longrightarrow \frac{a' f_{t - 1}}{\gcd(a', m') \gcd(f_{t - 1}, m')} \equiv \frac{b' f_t}{\gcd(b', m') \gcd(f_t, m')} \pmod {\frac{m'}{\gcd(a', m') \gcd(b', m')}}

且有

\frac{a' f_{t - 1}}{\gcd(a', m') \gcd(f_{t - 1}, m')} \equiv \frac{b' f_t}{\gcd(b', m') \gcd(f_t, m')} \pmod {\frac{m'}{\gcd(a', m') \gcd(b', m')}} \Longleftrightarrow \frac{a' f_{t - 1}}{\gcd(a', m') \gcd(f_{t - 1}, m')} \equiv \frac{b' f_t}{\gcd(b', m') \gcd(f_t, m')} \pmod {\frac{m'}{\gcd(f_{t - 1}, m') \gcd(f_t, m')}}

则

\frac{a' \gcd(b', m')}{\gcd(a', m') b'} \equiv \frac{\gcd(f_{t - 1}, m') f_t}{f_{t - 1} \gcd(f_t, m')} \pmod {\frac{m'}{\gcd(a', m') \gcd(b', m')}} \Longleftrightarrow \frac{a' \gcd(b', m')}{\gcd(a', m') b'} \equiv \frac{\gcd(f_{t - 1}, m') f_t}{f_{t - 1} \gcd(f_t, m')} \pmod {\frac{m'}{\gcd(f_{t - 1}, m') \gcd(f_t, m')}}

等式两边仅分别和 a', b', m' 与 f_{t - 1}, f_t, m' 有关，则将信息记为三元组 (\gcd(f_t, m'), \gcd(f_{t - 1}, m'), \frac{\gcd(f_{t - 1}, m') f_t}{f_{t - 1} \gcd(f_t, m')} \bmod m')，对每个 m' 用 std :: map 存下每个出现的三元组的 t 的最小值。

查询时在a', b' 对应的 m' 处的 map 里查 (\gcd(a', m'), \gcd(b', m'), \frac{a' \gcd(b', m')}{\gcd(a', m') b'} \bmod m') 存储的值即可。

由于 m' 显然仅会是 m 的因子，所以总时间复杂度为 O(\sigma(m) \log{n})（\sigma(n) = \sum\limits_{d \mid n} d），即 O(m \log{\log{m}} \log{n})

P2020 [NOI2011] 兔农

记斐波那契数列第 n 项为 f_n，题述序列第 n 项为 g_n。

考虑一个暴力的做法：初始令 g=f，每次找到第一个 g_P \equiv 1 \pmod k 的 P，令后续第 i 项减去 f_i。

那如何求后续第一个 \bmod k = 1 的项 g_P 呢？

考虑对于小于第一个 P 的部分，f=g，而对于第一个 P 满足 g_P \equiv 0 \pmod k，有 g_{P - 1} \equiv g_{P + 1} \equiv g_{P + 2} \pmod k，考虑小于第二个 P（记为 P'）的部分，有 g_{P + i} \equiv f_i \times g_{P + 1} \equiv f_i \times g_{P - 1} \pmod k，即考虑第一个 f_{pos} \times g_{P - 1} \equiv 1 \pmod k 的 pos，有 P' = P + pos。

于是只需重复这样的过程：

考虑若 \gcd(val, k) \not= 1 则 val 无逆元，pos 必然不存在，其余情况需要处理 f 中每个出现的 \bmod k 意义下的值。由于 k \le 10^6，根据斐波那契循环节相关知识，只需预处理前 O(k) 个元素即出现循环，也即处理完毕所有出现过的 \bmod k 意义下的值。

于是可以轻易维护上述过程。但 n \le 10^{18}，上述过程效率仍不够高。

考虑每次过程的贡献只和 val 的取值有关，而 val < k，则该过程执行 k 次后必出现重复 val，即进入循环，考虑将过程中减去的贡献利用矩阵合并起来，则多个循环可以一起处理，时间复杂度降为 O(k \log{k})。