HDU 1316 How Many Fibs? .

How Many Fibs?

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1212    Accepted Submission(s): 501

Problem 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^100. 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

 

 

Source

University of Ulm Local Contest 2000

 

 

Recommend

Eddy

 

听到KID既大数题目题目推荐！我都用STL写左一个有加法重载既大数类。

不过令我WA多次既问题竟然系读错题目{=     =b}，f2 = 1，结果WA多次，真系…………

下面直接贴代码：

 

4281094

2011-07-28 20:00:08

Accepted

1316

156MS

416K

2614 B

C++

10SGetEternal{（。）（。）}!

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define MAXI 486

class Bnum
{
public :

	vector<int> n;
	int l;

	Bnum(string str = "0")
	{
		int i;

		l = str.length();
		n.resize(l);
		for (i = 0; i < l; i++)
			n[i] = str[l - i - 1] - 48;
	}

	Bnum & operator = (Bnum &o)
	{
		l = o.l;
		n = o.n;

		return o;
	}

	friend Bnum operator + (Bnum a, Bnum b)
	{
		Bnum c;
		int i, len = a.l > b.l? a.l: b.l;

		c.l = len + 1;
		c.n.resize(c.l);
		a.n.resize(c.l);
		b.n.resize(c.l);
		for (c.n[len] = i = 0; i < len; i++)
		{
			c.n[i] += a.n[i] + b.n[i];
			c.n[i + 1] = c.n[i] / 10;
			c.n[i] %= 10;
		}
		if (!c.n[c.l - 1]) c.n.resize(--c.l);

		return c;
	}

	friend bool operator < (Bnum a, Bnum b)
	{
		int i;

		if (a.l == b.l)
		{
			for (i = a.l - 1; i >= 0; i--)
				if (a.n[i] < b.n[i]) return 1;
				else if (a.n[i] > b.n[i]) return 0;
			return 0;
		}
		else return a.l < b.l;
	}

	friend bool operator > (Bnum a, Bnum b)
	{
		int i;

		if (a.l == b.l)
		{
			for (i = a.l - 1; i >= 0; i--)
				if (a.n[i] > b.n[i]) return 1;
				else if (a.n[i] < b.n[i]) return 0;
			return 0;
		}
		else return a.l > b.l;
	}

	friend bool operator == (Bnum a, Bnum b)
	{
		int i;

		if (a.l == b.l)
		{
			for (i = a.l - 1; i >= 0; i--)
				if (a.n[i] != b.n[i]) return 0;
			return 1;
		}
		else return 0;
	}

	friend bool operator <= (Bnum a, Bnum b) { return a == b || a < b; }
	friend bool operator >= (Bnum a, Bnum b) { return a == b || a > b; }

	friend ostream & operator << (ostream & output, Bnum &o)
	{
		int i;

		for (i = 0; i < o.l; i++)
			output << o.n[o.l - i - 1];

		return output;
	}

	friend istream & operator >> (istream & input, Bnum &o)
	{
		string buf;

		input >> buf;
		o = Bnum(buf);

		return input;
	}

}fin[MAXI];

void init()
{
	int i;

	fin[1] = Bnum("1");
	fin[2] = Bnum("2");
	for (i = 3;; i++)
		if (fin[i - 1].l >= 102) break;
		else fin[i] = fin[i - 1] + fin[i - 2];
}

int main()
{
	int i, sum;
	Bnum a, b;

	init();
	while (cin >> a >> b)
	{
		if (a == Bnum("0") && b == Bnum("0")) break;
		for (sum = 0, i = 1; i < MAXI; i++)
			if (fin[i] > b) break;
			else if (a <= fin[i] && fin[i] <= b)
				sum++;
		cout << sum << endl;
	}

	return 0;
}

 下面贴上K神关于呢个题目既博文！！！

http://972169909-qq-com.iteye.com/blog/1133478