[CodeChef OCT13]斐波那契数Fibonacci Number解题报告

题目


分析

这道题是CodeChef上难得一见的优美数论题,比那些(净是中国人出的)丧心病狂的数据结构高到不知道哪里去了。

题目基于两个算法:第一个是Tonelli-Shanks算法,第二个是Shanks大步小步算法(这个Shanks是会玩的)。前者参见我的上一篇博文:http://blog.csdn.net/wmdcstdio/article/details/49862189,后者资料众多,不再赘述。
Tonelli-Shanks算法是一个“开根号”的算法。即,给出奇素数p和某个a,它能在O(log^2p)内找到一个r,使得r^2=a (mod p),或者判断不存在这样的r。而大步小步算法则是求“离散对数”的:给出a,b,求最小的非负整数n使得a^n=b (mod p)。
Tonelli-Shanks算法能干什么呢?首先可以求出模P意义下的“根号5”,即某个x使得x^2=5 (mod P,下略),然后就能求出模P意义下的”(sqrt(5)+1)/2″,记为y。

如此一来,我们可以把Fibonacci数列的通项公式写成:
Fn=(1/x)*(y^n-(-1/y)^n),其中的“除法”自然就是乘以乘法逆元的意思。
我们需要求出最小的非负整数n,使得Fn=c,把通项公式中的x乘过去,就是C*x=y^n-(-1/y)^n。

先假设n是偶数(n是奇数的情况非常类似,把它作为练习留给读者)。设C*x=d,我们的方程变成了:
d=y^n-1/(y^n).
在这里就可以看出来我们要做什么了,再写开一点:
设u=y^n,则d=u-1/u,u^2-du-1=0,这是一个标准的一元二次方程!只是它是在模P意义下的。
怎么解这个一元二次方程呢?
回想(实数系下)一元二次方程的求根公式,没错就是初中数学毒瘤题经常用的那个:(-b±sqrt(b^2-4ac))/2a,其中用到的操作无非加减乘除和开平方——这些操作,我们都能做!除法就是求逆元,开平方用Tonelli-Shanks。
于是我们得到了y^n的值。现在问题变成了:求最小的非负偶数n,使得y^n=u,当然可能的u有两个,即二次方程的两个根。
怎么解决“偶数”的问题呢?用Tonelli-Shanks把u开平方即可。当然你也可以先不管奇偶求一个n,然后再求y对P的阶数,试图累加。

如果你想这么做,还可以继续优化常数。这道题的主要复杂度来自于大步小步算法,可以主要由它下手:先把所有的u求出来,在一次大步小步算法中同时求解;以及把大步小步算法的map换成哈希表,都能有效减少常数。

代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注