钾肥喵的窝

我在 CODING 部署的 Hexo 博客

0%

斐波那契数列与皮萨诺周期

传送门

P4000 斐波那契数列

P4994 终于结束的起点

皮萨诺周期

皮萨诺周期(Pisano period), 即斐波那契数列对\(n\)取模的最小循环节, 通常用\(\pi(n)\)表示.

要解决P4000首先需要知道一些定理(具体证明):

\[ \begin{align} \pi(mn) &= \pi(m)\cdot\pi(n), && (m, n互质)\\ \pi(p^{k}) &\mid \pi(p)\cdot p^{k-1}, &&(p是质数) \\ \pi(p) &\mid p-1, &&(p是质数, 且5对p存在二次剩余) \\ \pi(p) &\mid 2(p+1), &&(p是质数, 且5对p不存在二次剩余) \end{align} \]

将上述定理中的整除换成等号计算, 接着枚举因数即可找出最小循环节, 也即皮萨诺周期.

求解

P4000

首先对\(p\)进行因式分解, 得到\(p=\sum_{1}^{m}p_{i}^{k_{i}}\), 接着求得\(\pi_i=\pi(p_{i}^{k_{i}})\), 再求\(len = \mathrm{lcm}(\pi_1, \dots, \pi_{m})\), 这就是一个循环节(不一定是最小, 但对本题来说影响不大).

接着使用矩阵快速幂求\(fib(len)\ \mathrm{mod}\ p\)即可.

P4994

\(len\)的过程同P4000, 接着枚举\(len\)的因子并判断即可.