菲波那契數列(2)-基本算法之遞歸變遞推

總時間限制: 1000ms 記憶體限制: 65536kB

描述

菲波那契數列是指這樣的數列: 數列的第一個和第二個數都為1，接下來每個數都等于前面2個數之和。

給出一個正整數a，要求菲波那契數列中第a個數對1000取模的結果是多少。

輸入

第1行是測試資料的組數n，後面跟着n行輸入。每組測試資料占1行，包括一個正整數a(1 <= a <= 1000000)。

輸出

n行，每行輸出對應一個輸入。輸出應是一個正整數，為菲波那契數列中第a個數對1000取模得到的結果。

樣例輸入

4

5

2

19

1

樣例輸出

5

1

181

1

#include<iostream>
using namespace std;
//http://noi.openjudge.cn/ch0203/1760/
//有意思，原來這個數列每次%1000然後再計算的值是不變的
//開始不用求餘的結果計算的時候遇到大數會輸出負數，也就是越界 
int n;
typedef long long ll;
ll a,k,b[];
void f(ll x){
    for(;x<=a;x++){
        b[x]=(b[x-]+b[x-])%;
    }
}
int main(){
    cin>>n;
    b[]=;
    b[]=;
    b[]=;
    k=;
    while(n--){
        cin>>a;
        if(a<=k)cout<<b[a]%<<endl;
        else{
            f(k);
            k=a;
            cout<<b[a]%<<endl;
        }
    }
}