hrefspace

 找回密码
 立即注册
搜索
热搜: PHP PS 程序设计
查看: 856|回复: 9

fibonacci(10^14) % 1234567891011是多少?

[复制链接]

484

主题

491

帖子

1493

积分

大司空

Rank: 5Rank: 5

积分
1493
发表于 2024-1-9 17:11:10 | 显示全部楼层 |阅读模式
如题:
我知道有个公式直接计算fibonacci第n项,可能是这个数太大了,可我还是计算不出来.不知道该怎么求?
.

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

0

主题

220

帖子

86

积分

关内侯

Rank: 2

积分
86
发表于 2024-1-9 17:12:01 | 显示全部楼层
Fibonacci 直接公式含有无理数,不便计算。

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

使用道具 举报

0

主题

179

帖子

4

积分

新手上路

Rank: 1

积分
4
发表于 2024-1-9 17:12:43 | 显示全部楼层
1# gracias

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

0

主题

192

帖子

2

积分

新手上路

Rank: 1

积分
2
发表于 2024-1-9 17:13:13 | 显示全部楼层
1# gracias


wayne 发表于 2012-2-20 13:47 [url=http://bbs.emath.ac.cn/redirect.php?goto=findpost&pid=41738&ptid=4054][/url]
这里用这个公式用处不大,要用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)]$

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

0

主题

184

帖子

15

积分

新手上路

Rank: 1

积分
15
发表于 2024-1-9 17:13:27 | 显示全部楼层
根据3楼的公式,fibonacci(10^14)有20万亿位数字,我们的PC显然无法计算。一个可行的做法是,从1开始,每计算几项就求做一次模运算,直到计算到10^14。
回复

使用道具 举报

0

主题

192

帖子

2

积分

新手上路

Rank: 1

积分
2
发表于 2024-1-9 17:13:44 | 显示全部楼层
根据3楼的公式,fibonacci(10^14)有20万亿位数字,我们的PC显然无法计算。一个可行的做法是,从1开始,每计算几项就求做一次模运算,直到计算到10^14。
liangbch 发表于 2012-2-20 19:24 [url=http://bbs.emath.ac.cn/redirect.php?goto=findpost&pid=41744&ptid=4054][/url]

这个问题郭肯定能解决的,因为郭的素性判定算法用到了!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

0

主题

173

帖子

2

积分

新手上路

Rank: 1

积分
2
发表于 2024-1-9 17:14:39 | 显示全部楼层
这个问题,对于郭,是相当简单的,和模幂算法应该差不多!
回复

使用道具 举报

0

主题

179

帖子

4

积分

新手上路

Rank: 1

积分
4
发表于 2024-1-9 17:14:54 | 显示全部楼层
其中肯定用到了二进制!
回复

使用道具 举报

0

主题

212

帖子

2

积分

新手上路

Rank: 1

积分
2
发表于 2024-1-9 17:15:15 | 显示全部楼层
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))
回复

使用道具 举报

0

主题

173

帖子

2

积分

新手上路

Rank: 1

积分
2
发表于 2024-1-9 17:15:45 | 显示全部楼层
发现这个题目里面模1234567891011不是素数,而且素因子都不大,所以也可以采用wayne在楼上的方法了。
不过还是直接采用4#的方法效率高,只要对n-1采用二进制表示,然后采用通常计算模幂的方法计算出矩阵的n-1次方即可。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|hrefspace

GMT+8, 2024-11-24 06:12 , Processed in 0.074748 second(s), 23 queries .

Powered by hrefspace X3.4 Licensed

Copyright © 2022, hrefspace.

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