PAT乙級(Basic Level)練習題 斐波那契鳳尾

斐波那契鳳尾

時間限制 3000 ms  記憶體限制 32768 KB  代碼長度限制 100 KB  判斷程式 Standard  (來自 小小)

題目描述

NowCoder号稱自己已經記住了1-100000之間所有的斐波那契數。

為了考驗他，我們随便出一個數n，讓他說出第n個斐波那契數。當然，斐波那契數會很大。是以，如果第n個斐波那契數不到6位，則說出該數；否則隻說出最後6位。      

輸入描述:

輸入有多組資料。

每組資料一行，包含一個整數n (1≤n≤100000)。      

輸出描述:

對應每一組輸入，輸出第n個斐波那契數的最後6位。      

輸入例子:

1
2
3
4
100000      

輸出例子:

1
2
3
5

537501


       
#include <cstdio>
const int maxn=100000+10;
int a[maxn];

int main(){
    int n;
    a[1]=1;
    a[2]=2;
    for(int i=3;i<=100000;i++) a[i]=(a[i-1]+a[i-2])%1000000;
    while(scanf("%d",&n)==1){
        if(n>=30) printf("%06d\n",a[n]);
        else printf("%d\n",a[n]);
    }
    return 0;
}