hdu 3117 Fibonacci Numbers

点击此处即可传送到hdu 3117

                  **Fibonacci Numbers**


Problem Description

The Fibonacci sequence is the sequence of numbers such that every element is equal to the sum of the two previous elements, except for the first two elements f0 and f1 which are respectively zero and one.



What is the numerical value of the nth Fibonacci number? 



Input

For each test case, a line will contain an integer i between 0 and 108 inclusively, for which you must compute the ith Fibonacci number fi. Fibonacci numbers get large pretty quickly, so whenever the answer has more than 8 digits, output only the first and last 4 digits of the answer, separating the two parts with an ellipsis (“...”). 

There is no special way to denote the end of the of the input, simply stop when the standard input terminates (after the EOF).





Sample Input

0
1
2
3
4
5
35
36
37
38
39
40
64
65





Sample Output

0
1
1
2
3
5
9227465
14930352
24157817
39088169
63245986
1023...4155
1061...7723
1716...7565

题目大意：就是给你一个数如果<10^8就正常输出它的斐波那契数，否则就输出前四位和后四位

解题思路：矩阵连乘和封闭公式结合：
f(n)=1/sqrt(5)(((1+sqrt(5))/2)^n+((1-sqrt(5))/2)^n)

具体详见代码：

/*
2015 - 8 - 13 下午
Author: ITAK
今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
*/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
LL Fei[100];
const int mod = 10000;
const int maxn = 2;
typedef struct
{
    LL m[maxn][maxn];
} Matrix;

Matrix P = {0,1,
            1,1
           };
Matrix I = {1,0,
            0,1
           };
Matrix Mat_mul(Matrix a, Matrix b)//矩阵乘法
{
    int i, j, k;
    Matrix c;//计位
    for(int i=0; i<maxn; i++)
        for(int j=0; j<maxn; j++)
        {
            c.m[i][j] = 0;
            for(int k=0; k<maxn; k++)
                c.m[i][j] += (a.m[i][k]*b.m[k][j])%mod;
            c.m[i][j] %= mod;
        }
    return c;
}
Matrix quick_mod(LL n)//快速幂
{
    Matrix m = P, ans = I;
    while(n)
    {
        if(n & 1)
            ans = Mat_mul(ans, m);
        n >>= 1;
        m = Mat_mul(m,m);
    }
    return ans;
}
int main()
{
    double log_s = 0.0;
    Matrix tmp;
    int n, bit=0;
    Fei[0] = 0;
    Fei[1] = 1;
    for(int i=2; i<40; i++)
        Fei[i] = Fei[i-1]  +Fei[i-2];
    while(~scanf("%d",&n))
    {
        if(n < 40)
            printf("%d\n",Fei[n]);
        else
        {
            tmp = quick_mod(n);
            int ans_e = tmp.m[0][1];
            log_s=log10(1.0/sqrt(5)) + (double)n*log10((1.0+sqrt(5))/2.0);
            int ans_s=(int)(pow(10,log_s-(int)log_s+3));
            printf("%d",ans_s) ;
            printf("...");
            printf("%04d\n",ans_e);
        }
    }
    return 0;
}