Fibonacci

题意：

求解斐波那契数列第$n$项的前4位数字。

解法：

注意到只需要求解前几位数字，这样只要求出$log_{10}{ans}$而后取小数部分$x$，再求出$[10^x * 1000]$即可。

关键在于求解$log_{10}{F_n}$：

1.由数列特征根得

$F_n = frac{1}{ sqrt{5} } ( {x_1}^n - {x_2}^n ) $

$x_1,x_2$为方程$x^2 = x+1$的解，假定$x_1$为较大的解。

注意到${x_2}^n$是收敛的，这样可以直接计算出其值，而对于${x_1}^n$则难以计算。

这样对原式化简得

$F_n = frac{1}{sqrt{5}} {x_1}^n (1 - (frac{x_2}{x_1})^n )$

左右取$log_{10}$即可。

2.由极限分析得，$lim_{x o infty}{ frac{F_{n+1}}{F_n} } = phi$

从而有$F_n approx F_t * {phi}^{n-t}$

左右取$log_{10}$即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define LD long double

using namespace std;

LD qpow(LD x,int n)
{
    LD ans=1;
    for(;n;n>>=1,x*=x)
        if(n&1) ans*=x;
    return ans;
}

int n;

int main()
{
    while(~scanf("%d",&n))
    {
        if(n==0)
        {
            puts("0");
            continue;
        }
        LD rt5 = sqrt(5);
        LD log_Fn = -log10(rt5) + n*(LD)log10((rt5+1)/2);
        log_Fn += log10(1 - qpow((1-rt5)/(rt5+1),n));
        LD tmp = (double)pow(10,log_Fn);
        if(tmp <= 10000.0)
        {
            cout << (int)tmp << endl;
            continue;
        }
        log_Fn -= floor(log_Fn);
        cout << (int)(pow(10,log_Fn)*1000.0) << endl;
    }
    return 0;
}