斐波那契数列

题目描述
时间限制: 5 Sec 内存限制: 128 MB
小牛：“话说，斐波那契数列1, 1, 2, 3, 5, 8, 13…是一个神奇的数列，它的……” ！@#￥%……&（小牛被众人群殴——“就这玩意，谁不懂啊？”） 小牛：“咳咳，这可是我的地盘，听我的！这是一道水题，要求输入正数n，输出相应的第n个（从1计）斐波那契数。” ！@#￥%……&（小牛再次被众人群殴——“去……水题水题！”）
输入
若干（不超过1000）行，每行一个正整数n（1 <= n <= 100000），以0表示输入的结尾。
输出
相应的第n个斐波那契数，每个一行。
样例输入
1
2
3
4
5
0
样例输出
1
1
2
3
5
提示
1、请注意，输入数据不超过1000行。
2、输入虽然是“1 2 3 4 5”，但输出显然不是“上山打老虎”。
3、小牛会使用很卑鄙的（其实是被逼的）输入数据来欺负你，所以你必须比小牛更卑鄙！

这道题很无趣，考的就是大数的压位，开始写没注意数据范围爆了long long，然后打表内存也超出，于是尝试大数+迭代，但开始用的char型大数，时间超了，再改int型大数，发现还是超，最后才改成压位的大数过了。

#include <cstdio>  
#include <algorithm>  
#include <cmath>  
#include <iostream>  
#include <map>   
#include <queue>  
#include <cstdlib>  
#include <cstring>  
#include <string>  
#include <ctime>  
#include <vector>  

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const ll MOD = 1000000009;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-8;

const ll power = 15;     
const ll base = 1e15;    

const int MAXN = 2000; 
struct BigNum  
{  
    ll a[MAXN];  
    BigNum(){ 
        memset(a,0,sizeof(a)); 
    }                 
    BigNum(char *s){  
        memset(a,0,sizeof(a));  
        int len=strlen(s);  
        a[0]=(len+power-1)/power;     
        for(ll i=0,t=0,w;i<len;w*=10,++i){  
            if(i%power==0){
                w=1,++t; 
            }  
            a[t]+=w*(s[i]-'0');  
        }  
    }  
    void print(){  
        printf("%lld",a[a[0]]);        
        for (int i=a[0]-1;i>0;--i)  
        printf("%0*lld",power,a[i]);     
        printf("\n");  
    }  
};  

struct Node{
    int a1,before;
    BigNum ans;
};

bool cmp1(Node x,Node y){
    return x.a1<y.a1;
}

bool cmp2(Node x,Node y){
    return x.before<y.before;
}  
BigNum operator + (const BigNum &p,const BigNum &q){  
    BigNum c;  
    c.a[0]=max(p.a[0],q.a[0]);  
    for(int i=1;i<=c.a[0];++i){  
        c.a[i]+=p.a[i]+q.a[i];  
        c.a[i+1]+=c.a[i]/base;  
        c.a[i]%=base;  
    }  
    if(c.a[c.a[0]+1]) 
        ++c.a[0];  
    return c;  
}  

Node q[1005];
int main(){
    int n=0,k;
    while(cin>>k){
        if(k==0)
            break;
        q[n].a1=k;
        q[n].before=n;
        n++;
    }
    sort(q,q+n,cmp1);
    char b[]="1";
    BigNum s1(b),s2(b),temp;
    int j=3;
    for(int i=0;i<n;i++){
        if(q[i].a1==1||q[i].a1==2){
            q[i].ans=s1;
        }
        else{
            for(;j<=q[i].a1;j++){
                temp=s1;
                s1=s2;
                s2=temp+s1;
            }
            q[i].ans=s2;
        }
    }
    sort(q,q+n,cmp2);
    for(int i=0;i<n;i++){
        q[i].ans.print();
    }
    return 0;
}