UVA 10183 How Many Fibs?

1981 ワード

标题:[a,b]の間のFibonacci numbersを求めて、範囲が10^100に達して、高精度を使って、それからテストして、500個目になる時、長さはすでに105になって、だから私達は500個目まで計算すればいいので、ついでに高精度を復習しました
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

char fib[550][170];

void Add(char *a,char *b,char *res){
    int lena = strlen(a),lenb = strlen(b);
    int x,i,y = 0;
    for (i = 0; i < lena || i < lenb || y; i++){
       x = y;
       if (i < lena)
           x += a[i] - '0';
       if (i < lenb)
           x += b[i] - '0';
       y = x / 10;
       res[i] = x % 10 + '0';
    }
    res[i] = '\0';
}

void Reverse(char *result){
    int len = strlen(result);
    int b = len>>1;
    for (int i = 0; i < b; i++){
        char temp = result[i];
        result[i] = result[len-1-i];
        result[len-1-i] = temp;
    }
}

int cmp(char *a,char *b){
    int lena = strlen(a);
    int lenb = strlen(b);
    if (lena < lenb)
        return 1;
    if (lena > lenb)
        return -1;
    if (lena == lenb){
        for (int i = 0; i < lena; i++)
            if (a[i] < b[i])
                return 1;
            else if (a[i] > b[i])
                return -1;
    }
    return 0;
}

int main(){
    fib[1][0] = '1';
    fib[2][0] = '2';
    Reverse(fib[1]);
    Reverse(fib[2]);
    for (int i = 3; i <= 500; i++)
        Add(fib[i-1],fib[i-2],fib[i]);
    for (int i = 1; i <= 500; i++)
        Reverse(fib[i]);
    char a[200],b[200];
    while (scanf("%s%s",a,b) != EOF){
        if (a[0] == '0' && b[0] == '0')
            break;
        int count = 0;
        for (int i = 1; i <= 500; i++){
            if (cmp(fib[i],b) < 0)
                break;
            if (cmp(a,fib[i]) >= 0)
                count++;
        }
        printf("%d
",count); } return 0; }