找回密码
 欢迎注册
查看: 30598|回复: 137

[求助] fibonacci(10^14) % 1234567891011是多少?

[复制链接]
发表于 2012-2-20 12:32:00 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
如题:
我知道有个公式直接计算fibonacci第n项,可能是这个数太大了,可我还是计算不出来.不知道该怎么求?
.
精华
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-20 13:26:26 | 显示全部楼层
Fibonacci 直接公式含有无理数,不便计算。

可用矩阵推导其递推式,得到一个整数矩阵的幂,
再用矩阵的模幂计算即可,非常快速。

评分

参与人数 1威望 +12 鲜花 +12 收起 理由
wayne + 12 + 12

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-20 13:47:44 | 显示全部楼层
1# gracias

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-20 16:26:20 | 显示全部楼层
1# gracias


wayne 发表于 2012-2-20 13:47

这里用这个公式用处不大,要用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)]$

评分

参与人数 1威望 +12 鲜花 +12 收起 理由
wayne + 12 + 12

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-20 19:24:03 | 显示全部楼层
根据3楼的公式,fibonacci(10^14)有20万亿位数字,我们的PC显然无法计算。一个可行的做法是,从1开始,每计算几项就求做一次模运算,直到计算到10^14。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-20 20:13:47 | 显示全部楼层
根据3楼的公式,fibonacci(10^14)有20万亿位数字,我们的PC显然无法计算。一个可行的做法是,从1开始,每计算几项就求做一次模运算,直到计算到10^14。
liangbch 发表于 2012-2-20 19:24


这个问题郭肯定能解决的,因为郭的素性判定算法用到了!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-20 20:16:16 | 显示全部楼层
这个问题,对于郭,是相当简单的,和模幂算法应该差不多!

评分

参与人数 1威望 +12 鲜花 +12 收起 理由
wayne + 12 + 12

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-20 20:16:36 | 显示全部楼层
其中肯定用到了二进制!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-20 22:27:24 | 显示全部楼层
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))
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-20 22:33:02 | 显示全部楼层
发现这个题目里面模1234567891011不是素数,而且素因子都不大,所以也可以采用wayne在楼上的方法了。
不过还是直接采用4#的方法效率高,只要对n-1采用二进制表示,然后采用通常计算模幂的方法计算出矩阵的n-1次方即可。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-7-23 07:56 , Processed in 0.047255 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表