学步园

http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=2&sectionid=2&problemid=1

首先Fibonacci数列的通项公式是，公式推导方法在http://baike.baidu.com/view/816.htm#2_3。

然后看公式 loga(b^m) = m*loga(b)，loga(m*n) = loga(m) + loga(n) 。

比如一个数是123456789，log10(123456789)=log10(1.23456789*10^8)=log10(1.23456789)+8。

log10(1.23456789)为log10(123456789)的小数部分，再10^log10(1.23456789)得1.23456789，由此可见要求它的前4位数，只需再乘以1000后强制转换成int类型就是1234了。

先对前20项做统计保存在数组fac中，然后对于从第21项开始以后的数，对an按10取对数得 log10(an) = -0.5*log10(5) + n*log10(f)，其中f=(sqrt(5.0)+1)/2.0。

#include<stdio.h>
#include<math.h>
#define LOCAL
int fac[21]={0,1,1};

int main()
{
    #ifdef LOCAL
    freopen("fibonacci.in.txt", "r", stdin);
    #endif // LOCAL
    int n, i;
    double f = (sqrt(5.0)+1.0) / 2.0;
    double an;
    for(i=3; i<=20; i++)
        fac[i]=fac[i-1]+fac[i-2];
    while(scanf("%d", &n)!=EOF)
    {
        if(n<21)
            printf("%d\n", fac[n]);
        else
        {
            an = -0.5*log(5.0)/log(10.0) + (double)n*log(f)/log(10.0);
            an = an - floor(an);
            an = pow(10,an);
            an *= 1000;
            printf("%d\n", (int)an);
        }
    }
    return 0;
}