hdu 1316多少个小谎？(高精度斐波那契数)

// 大数继续

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

/**********************

高精度斐波数，依然用高精度的加法模板打表，打到520多就够了，

主要是判断数的大小，这里是比较额字符串形式的数的大小。

***********************/

Code:

#include<iostream> #include <stdio.h> #include<string> using namespace std; string add(string x,string y) { string ans ; int lenx = x.length(); int leny = y.length(); if(lenx<leny) { for(int i = 1;i<=leny-lenx;i++) x = '0'+x; } else { for(int i = 1;i<=lenx-leny;i++) y = '0'+y; } lenx = x.length(); int cf = 0; int temp; for(int i = lenx-1;i>=0;i--) { temp = x[i] - '0' + y[i] - '0'+cf; cf = temp/10; temp%=10; ans = char('0'+temp)+ans; } if(cf!=0) ans = char(cf+'0')+ans; return ans; } int compare(string x,string y)// 字符串形式的数的比较大小 { int i,lenx = x.length(),leny = y.length(),leaf; if(x==y) return 0;// 0 表示 x == y if(x.length()>y.length()) return 1;// 返回1 表示 x > y if(x.length()<y.length()) return -1;// -1 表示 x < y if(x.length()==y.length()) { for(i = 0;i<lenx;i++) { if(x[i]==y[i]) continue; if(x[i]>y[i]) return 1; else return -1; } return 0; } return leaf; } int main() { int i,j,k,start,eend; string x,y,num[1005];; num[0] = '0'; num[1] = '1'; num[2] = '2'; for(int i = 3;i<=1000;i++) num[i] = add(num[i-1],num[i-2]); while(cin>>x>>y&&x!='0'||y!='0')// x y 均为 0 的时候才结束程序 { if(y == '0')// y == 0 时 直接输出 0 { printf('0'); continue; } start = eend = 0; /** j = k = 0; while(x[j]=='0')// 受到 j++; x = x.substr(j,x.length()-j);// 受到 hdu 1753 的影响，以为会有前导0，其实没有 while(y[k]=='0') k++; y = y.substr(k,y.length()-k); **/ for(i = 1;i<1000;i++) { if(compare(x,num[i])==0) { start = i; break; } else if(compare(num[i],x)==-1&&compare(num[i+1],x)==1) { start = i+1; break; } } for(i = 1;i<1000;i++) { if(compare(y,num[i])==0){ eend = i;break; } else if(compare(num[i],y)==-1&&compare(num[i+1],y)==1){ eend = i;break; } } if(x=='0') // 注意 x == 0 时的情况 start = 1; //cout<<start<<' '<<eend<<endl;; cout<<eend-start+1<<endl; } }