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;
}