数論---フィボナの数列の公式の変形

Fibonacci
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3515    Accepted Submission(s): 1601
Problem Description
2007年が来ました.2006年1年間の修練を経て、数学の神童zouyuはついに0から1000000のFibonacciを数列に並べた.
(f[0]=0,f[1]=1;f[i]=f[i]+f[i-2](i>=2))の値はすべて暗記された.
次に、CodeStarは彼を試験することにしたので、彼に数字を聞くたびに、彼は答えを言わなければなりませんが、ある数字は長すぎます.だから4位を超えたのは上位4位を言えばいいのに、CodeStar自身は覚えていない.そこで彼はzouyuの言うことが正しいかどうかをテストするためにプログラムを書くことにした.
 
 
Input
数n(0<=n<=10000000)の数を入力し、1行ずつ入力します.ファイルの最後まで読みます.
 
 
Output
f[n]の最初の4つの数字を出力します(4つ未満の数字であれば、すべて出力します).
 
 
Sample Input
0 1 2 3 4 5 35 36 37 38 39 40
 
 
Sample Output
0 1 1 2 3 5 9227 1493 2415 3908 6324 1023
 
 
Source
Happy 2007
 
 
 
Mean: 
略 
analyse:
 この問題はfibonacci数列の公式を使う必要があります:F(n)=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}
この式の後半: - [(1-√5)/2]^nの誤差は0~1の間であるが、nが比較的大きい場合、彼の誤差は小さいので、一般的には無視できる.
式は、F(n)=(1/√5)*[(1+√5)/2]^n]になります.
この問題は私たちが上位4位を出力する必要があります.直接公式を使うと必ず超えますから、変形します.

  m^n=10^(n*log10(m));
  n*log10(m)   ，      ， 10   ，       m^n    ，   10   4    

 
Time complexity:O(n)
 
Source code:
 

//Memory   Time
// 1347K   0MS
// by : Snarl_jsb
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define MAX 1100
#define LL long long
using namespace std;

int main()
{
//    freopen("C:\\Users\\ASUS\\Desktop\\cin.txt","r",stdin);
//    freopen("C:\\Users\\ASUS\\Desktop\\cout.txt","w",stdout);
    int a[25];
    a[0]=0,a[1]=1;
    for(int i=2;i<=21;i++)
        a[i]=a[i-1]+a[i-2];
    int n;
    while(~scanf("%d",&n))
    {
        if(n<=20)
        {
            printf("%d
",a[n]);
            continue;
        }
       double x=sqrt(5*1.0); double y=log10(1/x);
       double z=n*log10(((x+1)/2));double p=y+z;
       double q=p-(int)p;double xx=pow(double(10),q);
       for(int i=1;;++i)
       {
         xx*=10;
         if(xx>10000)
             break;
       }
       printf("%d
",((int)xx)/10);
    }

    return 0;
}