数論(fabonacci数列)hdu-1156 8-Fibonacci

テーマリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=1568
 
タイトルの意味:
iを一つあげて、i番目のfebonacci数の上位四位を求めます.四位未満の直接出力です.
 
問題解決の考え方:
feibonacciで数列の通項式an=1/√5*((((((((1+√5)/2)^n+(√5-1)/2)^n)
nが大きいときは捨てられます(√5-1)/2)^nは小さくなりますので、一つにならないと捨てられます.
log 10(an)=log 10(1/√5)+n*log 10(((1+√5)/2)=p
p=p 1+p 2(うちp 1はpの整数部分、p 2はpの小数点以下部分)であれば、10^(p 1+p 2)=10^p 1*10^p 2=anのうち、10^p 1はanの末尾のゼロとなり、除去後は高位の計算に影響しない.
詳細な処理はコードを参照してください.
 
コード:

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF (1<<30)

#define PI acos(-1.0)

using namespace std;

#define ba sqrt(5.0)



/*

freopen("data.in","r",stdin);

freopen("data.out","w",stdout);

*/



//fabonacci     an=1/√5*(((1+√5)/2)^n+((√5-1)/2)^n)

// n          （√5-1)/2)^n       ，   



int save[30];

int main()

{

    save[0]=0;

    save[1]=1;

    for(int i=2;i<20;i++)

    {

        save[i]=save[i-1]+save[i-2];

       // printf("%d
",save[i]);

    } //        5  ，        

    int n;



    while(scanf("%d",&n)!=EOF)

    {

        if(n<20)

        {

            printf("%d
",save[n]);

            continue;

        }

        double temp=log10(1.0/ba)+n*log10((ba+1.0)/2.0); //        



        temp-=floor(temp);//      ，   save[n]     

        temp=pow(10.0,temp); //         



        while(temp<1000) //          

            temp*=10;

        while(temp>=10000) //         

            temp/=10;

        printf("%d
",(int)temp);



    }



    return 0;

}