Fibonacci
时间限制：5000 ms  |  内存限制：65536 KB
描述
Fibonacci数列是满足如下条件的整数数列：


F0 = 0


F1 = 1


FN = FN-1+FN-2 (N≥2)


Fibonacci数列的前10项如下：


0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …


另一个求解Fibonacci数列的公式是：见下面帖子的图片


 


对于任意给定的整数N，请求出FN模10000的余数。


输入
输入包含多组测试数据。


每组数据占一行，仅包含一个整数n（0≤n≤1,000,000,000）最后一行为整数-1代表输入结束，不需要做处理。

输出
对于每组测试数据，输出FN模10000的余数。

样例输入
0
9
-1
样例输出
0
34

题目网址 http://www.

[ 本帖最后由 laoyang103 于 2011-10-15 15:22 编辑 ]

//2ms AC代码
#include <stdio.h>
struct Matrix
{
    int _11,_12;
    int _21,_22;
};
void Ride(const Matrix *src1,const Matrix *src2,Matrix *out)
{
    out->_11 = (src1->_11*src2->_11 + src1->_12*src2->_21)%10000;
    out->_12 = (src1->_11*src2->_12 + src1->_12*src2->_22)%10000;
    out->_21 = (src1->_21*src2->_11 + src1->_22*src2->_21)%10000;
    out->_22 = (src1->_21*src2->_12 + src1->_22*src2->_22)%10000;
}
void Power(Matrix *src,int n,Matrix *out)
{
    Matrix one = {1,1,1,0};
    if(n == 1)
    {
        *out = one;
        return ;
    }
    Power(src,n>>1,out);
    Matrix temp = *out;
    Ride(&temp,&temp,out);
    if(0 == n%2)
        return ;
    else
    {
        temp = *out;
        Ride(&temp,&one,out);
    }
}
int main()
{
    int i,j,n;
    while(scanf("%d",&n) && n >=0)
    {
        if(0 == n || 1 == n)
        {
            printf("%d\n",n);
            continue;
        }
        Matrix m1 = {1,1,1,0},res;
        Power(&m1,n-1,&res);
        printf("%d\n",res._11);
    }
    return 0;
}

接分...

不懂  来拿分

我相信老大不是为了解分来的

貌似见过这算法。

恩，Congratulations

但是 我没见过 觉得很新鲜而且很高效  所以拿来分享一下

农村来的 没见过世面 呵呵

MIT 算法导论网上公开课里提到过,可以看看,还带中文字幕的哦。

分。。。