题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1568

题意：如标题所示，求斐波那契数前四位，不足四位直接输出答案

斐波那契数列通式：

当n<=20的时候，不足四位，所以直接打表。

当n>20的时候，大于四位的时候，ans满足这个公式：ans=-0.5*log10(5.0)+num*1.0*log10((1+sqrt(5.0))/2.0);

这个公式是怎么来的呢？我们可以对an取10的对数，根据对数的性质。

log10（ans）=log10（1/sqrt（5)）+log10(((1+sqrt(5)）/2)^num-(（1-sqrt(5)）/2)^num))

log10（ans）=0-0.5*log10(5.0)+log10(((1+sqrt(5)）/2)^num-((1-sqrt(5)）/2)^num))，当num趋于无穷的的时候  。

lim((1-sqrt(5)）/2)^num)=0

log10（ans）=0-0.5*log10(5.0)+log10(((1+sqrt(5)）/2)^num)= -0.5*log10(5.0)+num*1.0*log10( (1+sqrt(5)）/2)，我们就得到了上文的公式。

这里说一下原理，x=123456789，那么y=log10(x)=1.23456789,这个时候将y*=1000，就得到了 y=1234.56789，求幂次和取对数互为逆运算，通过这个原理我们可以求前x的长度。

//Author: xiaowuga

#include <bits/stdc++.h>

#define maxx INT_MAX

#define minn INT_MIN

#define inf 0x3f3f3f3f

#define maxn

using namespace std;

typedef long long ll;

ll table[];

int main() {

    ios::sync_with_stdio(false);cin.tie();

    table[]=;table[]=;

    for(int i=;i<=;i++) table[i]=table[i-]+table[i-];

    ll num;

    while(cin>>num){

       if(num<=) cout<<table[num]<<endl;

        else{

            double ans=-0.5*log10(5.0)+num*1.0*log10((+sqrt(5.0))/2.0);

            ans=ans-(ll)ans;

            double a=pow(10.0,ans);

            a=*a;

            cout<<(ll)a<<endl;

        }

    }

    return ;

}

hdu3117：Fibonacci Numbers

这道题求斐波那契的数列的前四位和后四位，前四位和1568是一样的，后四位只需要把mod变成10000就行了，比较简单，直接看代码吧！！

//Author: xiaowuga

#include <bits/stdc++.h>

#define maxx INT_MAX

#define minn INT_MIN

#define inf 0x3f3f3f3f

#define n 2

#define MOD 10000

using namespace std;

typedef long long ll;

ll table[];

ll first_four(ll num){

     double ans=-0.5*log10(5.0)+num*1.0*log10((+sqrt(5.0))/2.0);

     ans=ans-(ll)ans;

     double a=pow(10.0,ans);

     a=*a;

     return (ll)a;

}

struct Matrix{

    ll mat[][];

    Matrix operator * (const Matrix & m) const{

        Matrix tmp;

        for(int i=;i<n;i++)

            for(int j=;j<n;j++){

                tmp.mat[i][j]=;

                for(int k=;k<n;k++){

                    tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%MOD;

                    tmp.mat[i][j]%=MOD;

                }

            }

        return tmp;

    }

};

Matrix POW(Matrix &m,ll k){

    Matrix ans;

    memset(ans.mat,,sizeof(ans.mat));

    for(int i=;i<n;i++) ans.mat[i][i]=;

    while(k){

        if(k&) ans=ans*m;

        k/=;

        m=m*m;

    }

    return ans;

}

int main() {

    ios::sync_with_stdio(false);cin.tie();

    table[]=;table[]=;

    for(int i=;i<=;i++) table[i]=table[i-]+table[i-];

    ll num;

    while(cin>>num){

       if(num<=) cout<<table[num]<<endl;

       else{

            cout<<first_four(num)<<"...";

            Matrix m;

            memset(m.mat,,sizeof(m.mat));

            m.mat[][]=m.mat[][]=m.mat[][]=;m.mat[][]=;

            Matrix ans=POW(m,num-);

            cout.fill('');

            cout.width();

            cout<<ans.mat[][]%MOD<<endl;

       }

    }

    return ;

}

hdu1568&&hdu3117 求斐波那契数前四位和后四位的相关教程结束。