uva 10236 斐波拉契素数问题 - 数据结构与算法

已结贴√ 问题点数：10 回复次数：17

uva 10236 斐波拉契素数问题

斐波那契素数
时限：8s
【题目描述】
斐波那契数列为1,1,2,3,5,8,13……，你可以看得出，除了第一第二个数以外，每个数都是前两个数的和。现在定义，斐波那契素数是指与其他比它小的斐波那契数都互质的斐波那契数，为2、3、5、13、89、233、1597、4181、28657、514229……
现在让你求出第i个斐波那契素数的前九为，若不足九位就全部输出；
【输入】
    输入共n行，每行一个整数i（1≤i≤22000）；
【输出】
    输出共n行，每行按要求输出第i个斐波那契素数；
【输入样例】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
【输出样例】
2
3
5
13
89
233
1597
4181
28657
514229
1346269
24157817
165580141
433494437
297121507
533162911
956722026
250473078
449455702
308061521
//----------------------------------------------
个人想法：用高精度计算斐波拉契数列，素数位置的斐波拉契数就是结果，试过前面几项可以，后面不知道行不行。
          但这种方法无疑是非常繁的，各位大牛有什么想法？？？？

搜索更多相关主题的帖子: 其他　

第 2 楼

得分:10

这个对你会有帮助：http://en.
GCD(F_n, F_m) = F_GCD(n, m)
Fibonacci_Prime[k] = Fibonacci[Prime[k]], k >= 3
再根据Fibonacci的通项公式(就是用黄金分割率表示的那个，这儿贴公式不方便，不写了～)，就可以求出前9位数字了。