How many Fibs?
Description
Recall the definition of the Fibonacci numbers:
Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a,b].
f1 := 1n-1
f2 := 2
fn := f
+ 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<=10100. 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
Mean:
给定两个整数a和b，统计区间[a,b]内有多少个斐波那契数。
analyse:
T由于这题输入的范围达到了10^100，必须要用高精度来做。
我们先把10^100以内的斐波那契数全部求出来，然后输入的sta,en后进行位置查找，最后把sta、en的位置相见就的答案。
Time complexity：O(n)
Source code：
/*
_ooOoo_
o8888888o
88" . "88
(| -_- |)
O\ = /O
____/`---'\____
.' \\| |// `.
/ \\||| : |||// \
/ _||||| -:- |||||- \
| | \\\ - /// | |
| \_| ''\---/'' | |
\ .-\__ `-` ___/-. /
___`. .' /--.--\ `. . __
."" '< `.___\_<|>_/___.' >'"".
| | : `- \`.;`\ _ /`;.`/ - ` : | |
\ \ `-. \_ __\ /__ _/ .-` / /
======`-.____`-.___\_____/___.-`____.-'======
`=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
.............................................
佛祖镇楼 BUG辟易
佛曰:
写字楼里写字间，写字间里程序员；
程序人员写程序，又拿程序换酒钱。
酒醒只在网上坐，酒醉还来网下眠；
酒醉酒醒日复日，网上网下年复年。
但愿老死电脑间，不愿鞠躬老板前；
奔驰宝马贵者趣，公交自行程序员。
别人笑我忒疯癫，我笑自己命太贱；
不见满街漂亮妹，哪个归得程序员？
*/
//Memory Time
// 1347K 0MS
// by : Snarl_jsb
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define MAX 1100
#define LL long long
using namespace std;
vector<string> fibs;
string fibs_add(string f1,string f2)
{
string buff;
int carry=0,len1=f1.length(),len2=f2.length();
for(int i=0;i<len1;i++)
{
carry=(f1[i]-'0')+(f2[i]-'0')+carry;
char c=carry%10+'0';
carry/=10;
buff.push_back(c);
}
for(int i=len1;i<len2;i++)
{
carry=(f2[i]-'0')+carry;
char c=carry%10+'0';
carry/=10;
buff.push_back(c);
}
if(carry)
buff.push_back('1');
return buff;
}
void fill_fibs()
{
string f1,f2;
f1.push_back('1');
f2.push_back('1');
fibs.push_back(f1);
fibs.push_back(f2);
while(f2.length()<105)
{
string tmp=fibs_add(f1,f2);
f1=f2;
f2=tmp;
fibs.push_back(f2);
}
fibs[0]="0";
int Size=fibs.size();
for(int i=0;i<Size;i++)
reverse(fibs[i].begin(),fibs[i].end());
}
int main()
{
// freopen("C:\\Users\\ASUS\\Desktop\\cout.txt","w",stdout);
// freopen("C:\\Users\\ASUS\\Desktop\\cout.txt","w",stdout);
fill_fibs();
string sta,en;
while(cin>>sta>>en,sta[0]-'0'||en[0]-'0')
{
int i=1,ans=0;
while(1)
{
if(fibs[i].length()>sta.length()) break;
else if(fibs[i].length()==sta.length()&&fibs[i]>=sta) break;
i++;
}
while(1)
{
if(fibs[i]==en) {ans++;break;}
if(fibs[i].length() > en.length()) break;
else if(fibs[i].length() == en.length() && fibs[i]>en) break;
i++;
ans++;
}
cout<<ans<<endl;
}
return 0;
}