fibonacci(10^14) % 1234567891011是多少?
如题:我知道有个公式直接计算fibonacci第n项,可能是这个数太大了,可我还是计算不出来.不知道该怎么求?
.
精妙的解答 Fibonacci 直接公式含有无理数，不便计算。
可用矩阵推导其递推式，得到一个整数矩阵的幂，
再用矩阵的模幂计算即可，非常快速。 1# gracias
http://upload.wikimedia.org/wikipedia/en/math/6/b/5/6b53a73248d35568fc4f1e561b127202.png
http://upload.wikimedia.org/wikipedia/en/math/9/8/a/98a1f6974f068111f6fdc922620ffc69.png 1# gracias
http://upload.wikimedia.org/wikipedia/en/math/6/b/5/6b53a73248d35568fc4f1e561b127202.png
http://upload.wikimedia.org/wikipedia/en/math/9/8/a/98a1f6974f068111f6fdc922620ffc69.png
wayne 发表于 2012-2-20 13:47 https://bbs.emath.ac.cn/static/image/common/back.gif
这里用这个公式用处不大，要用gxqcn的方法
${(F_{n+1}=F_n+F_{n-1}),(F_n=F_n):}$
所以得到
$[(F_{n+1}),(F_n)]=[(1,1),(1,0)][(F_n),(F_{n-1})]$
所以
$[(F_{n+1}),(F_n)]=[(1,1),(1,0)]^{n-1}[(F_2),(F_1)]=[(1,1),(1,0)]^{n-1}[(1),(1)]$ 根据3楼的公式，fibonacci(10^14)有20万亿位数字，我们的PC显然无法计算。一个可行的做法是，从1开始，每计算几项就求做一次模运算，直到计算到10^14。 根据3楼的公式，fibonacci(10^14)有20万亿位数字，我们的PC显然无法计算。一个可行的做法是，从1开始，每计算几项就求做一次模运算，直到计算到10^14。
liangbch 发表于 2012-2-20 19:24 https://bbs.emath.ac.cn/static/image/common/back.gif
这个问题郭肯定能解决的，因为郭的素性判定算法用到了！ 这个问题，对于郭，是相当简单的，和模幂算法应该差不多！ 其中肯定用到了二进制！ http://en.wikipedia.org/wiki/Pisano_period
http://oeis.org/A001175
Let the prime factorization of n be p1^e1...pk^ek. Then a(n) = lcm(a(p1^e1), ..., a(pk^ek)) 发现这个题目里面模1234567891011不是素数，而且素因子都不大，所以也可以采用wayne在楼上的方法了。
不过还是直接采用4#的方法效率高，只要对n-1采用二进制表示，然后采用通常计算模幂的方法计算出矩阵的n-1次方即可。