hdu 3977 Evil teacher (斐波那契数列循环节)

题目链接

题意:f[0] = 1,f[1] = 1,f[i] = f[i-1] + f[i-2] (i>=2),问最小的m满足f[n]%p==f[n+m]%p

思路:求斐波那契数列循环节。

参考了Acdreamer的博客_Fib数模n的循环节

对于一个正整数n,我们求Fib数模n的循环节的长度的方法如下:

(1)把n素因子分解,即

(2)分别计算Fib数模每个的循环节长度,假设长度分别是

(3)那么Fib模n的循环节长度

从上面三个步骤看来,貌似最困难的是第二步,那么我们如何求Fib模的循环节长度呢?

     这里有一个优美的定理:Fib数模的最小循环节长度等于,其中表示Fib数模素数的最小循环节长度。可以看出我们现在最重要的就是求

对于求我们利用如下定理:

   如果5是模的二次剩余,那么循环节的的长度是的因子,否则,循环节的长度是的因子。

顺便说一句,对于小于等于5的素数,我们直接特殊判断,loop(2)=3,loop(3)=8,loop(5)=20。

那么我们可以先求出所有的因子,然后用矩阵快速幂来一个一个判断,这样时间复杂度不会很大。

这道题是模板题。博客中的模板代码很好理解…

换成了自己比较熟悉的矩阵构造方式,以及代码风格。

需要注意的是下标是从0开始的,当验证k是否为循环节的时候,应该验证f[k]和f[k+1]

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz