杭电1568

题意：小于四位的斐波那契数fib(n)直接输出，大于四位的斐波那契数只输出最左边四位，n<100000000。

Analyse:跟1060相同原理。10^x=fib(n)（用通项公式），求出x。令y=3.·#￥%……—*(小数部分是x的小数部分），再输出10^y

#include<stdio.h>
#include<math.h>
#define C ((sqrt(5)+1)/2)
int fib(int n)
{
    return (int)( (pow( (sqrt(5)+1)/2 , n ) - pow( (1 - sqrt(5))/2 , n))/sqrt(5) );
}
int left4(int n)
{
    double x,y;//10的指数fib(n)==10^x
    x=n*log10(C)-0.5*log10(5);
    y=x-floor(x);
    y+=3;
    return (int)pow(10,y);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n<=20)
            printf("%d\n",fib(n));
        else
            printf("%d\n",left4(n));
    }
    return 0;
}