最近斐波那契数列的有关问题好多呀

最近斐波那契数列的问题好多呀！
http://www.51nod.com/question/index.html#!questionId=627

再来一道，这个问题更有意思。解决之后的成就感更强。

有一个无穷长的数列，元素是斐波那契数列 mod 10^13， 现在给出一个数值，求该数值在这个数列中第1次出现的位置。

该数列的起始项是:0.
0 1 1 2 3 5......

比如给出377，输出14，因为第14项是377
------解决方案--------------------
其实主要问题在于算mod 5^13
可以查看emath上的公式，可以看出2^(n-1)F_n(mod 5^13)可以写成一个n的25次多项式。其周期应该是4*5^13
而给定F_n=X(mod 5^13),我们可以先根据公式算出2^(n-1)F_n(mod 5)算出最小的n1,那么20k+n1就是所有的可能的n,然后再次模5^2,可以得出k(mod 5)的值，得出n必然是100k+n2的形式，一直上去即可。
而模2^13比较简单，因为周期不大
------解决方案--------------------
呵呵，仅限于理论分析，
另外关于其中周期可以参考链接:
http://www.math.temple.edu/~renault/fibonacci/fib.html
------解决方案--------------------
先暴力算出 mod 10^13 的循环节，然后就可以二分查找位置了，利用矩阵计算 fib(n) , 复杂度 O( (logn)^2 )
------解决方案--------------------
这个可以用递归来做吧，我写了个代码：
#include<stdio.h>

int fun(int n)
{
int sum1;

if(n==0)
{
return 0;
}
if(n==1)
{
return 1;
}
sum1=fun(n-1)+fun(n-2);
return sum1;
}

void main()
{
int n,sum=0;
scanf("%d",&n);
printf("%d\n",fun(n));
}