poj 2413 How many Fibs?

poj 2413 How many Fibs?

How many Fibs? Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10748 Accepted: 3982

Description

Recall the definition of the Fibonacci numbers:

f1 := 1 

f2 := 2 

fn := fn-1 + fn-2     (n>=3) 

Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a,b].

Input

The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a=b=0. Otherwise, a<=b<=10¹⁰⁰. The numbers a and b are given with no superfluous leading zeros.

Output

For each test case output on a single line the number of Fibonacci numbers fi with a<=fi<=b.

Sample Input

10 100
1234567890 9876543210
0 0

Sample Output

5
4

解題思路：

用一個字符串數組記錄位數小於101的所有fibs，然後對於給定的a，b，求出滿足條件的個數；

#include 
#include 
#include 
using namespace std;
char fibs[10005][102];
void add(int n){
	int len_a=strlen(fibs[n-1]),len_b=strlen(fibs[n-2]);
	int p=len_a-1,q=len_b-1;
	int a[102],left=0;
	for (int i=0;i<102;i++){
		a[i]=left;
		if (p>=0)
			a[i]+=fibs[n-1][p--]-'0';
		if (q>=0)
			a[i]+=fibs[n-2][q--]-'0';
		left=a[i]/10;
		a[i]%=10;
	}
	int i;
	for (i=101;i>=0;i--){
		if (a[i]!=0)
			break;
	}
	int k=0;
	while (i>=0){
		fibs[n][k++]=a[i--]+'0';
	}
	fibs[n][k]=0;
}
bool cmp(char *a,char *b){
	int len_a=strlen(a),len_b=strlen(b);
	if (len_a>len_b)
		return true;
	if (len_ab[n]-'0')
			return true;
		if (a[n]-'0'