菲波那契数列(2)-从递归到递推的算法转换

菲波那契数列(2)-基本算法之递归变递推

总时间限制: 1000ms 内存限制: 65536kB
描述
菲波那契数列具有如下特征: 其初始两项均为1，后续每一项数值等于前两项之和。
现给定一个正整数a，要求计算菲波那契数列中第a项对1000取模后的结果。
输入
第一行给出测试数据的组数n，随后n行分别提供对应的测试数据。每组测试数据占据一行，包含一个正整数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[1000005];
    void f(ll x){
    for(;x<=a;x++){