1533.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1533 on 2005-03-24 at 08:05:11 */ 
#include <stdio.h>

int numLen(long);

int main()
{
    long fib[2][120], order;
    int i, j, k, l, flag, len;
    
    while(scanf("%ld", &order) == 1){
        k = 0;
        for(i = 0; i < 2; i++){
            for(j = 0; j < 120; j++){
                fib[i][j] = 0;
            }
        }
        fib[0][119] = 1;
        fib[1][119] = 1;
        for(i = 2; i < order; i++){
            l = k;
            k = 1 - k;
            for(j = 119; j >= 0; j--){
                if((fib[k][j] != 0) || (fib[l][j] != 0)){
                    fib[k][j] += fib[l][j];
                    if(fib[k][j] > 1000000000){
                        fib[k][j-1] += fib[k][j] / 1000000000;
                        fib[k][j] %= 1000000000;
                    }
                }
            }
        }
        flag = 0;
        for(i = 0; i < 120; i++){
            if(fib[k][i] == 0){
                if(flag != 0){
                    for(j = 0; j < 9; j++){
                        printf("0");
                    }
                }
            }else if(fib[k][i] >= 100000000){
                flag = 1;
                printf("%ld", fib[k][i]);
            }else{
                if(flag != 0){    
                    len = 9 - numLen(fib[k][i]);
                    for(j = 0; j < len; j++){
                        printf("0");
                    }
                }
                printf("%ld", fib[k][i]);
                flag = 1;
            }
        }
        printf("\n");
    }

    return 0;
}

int numLen(long a)
{
    if(a >= 100000000){
        return 9;
    }else if(a >= 10000000){
        return 8;
    }else if(a >= 1000000){
        return 7;
    }else if(a >= 100000){
        return 6;
    }else if(a >= 10000){
        return 5;
    }else if(a >= 1000){
        return 4;
    }else if(a >= 100){
        return 3;
    }else if(a >= 10){
        return 2;
    }else if(a >= 1){
        return 1;
    }else{
        return 0;
    }
}