How Many Fibs?

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 3334    Accepted Submission(s): 1340

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

 

import java.math.BigDecimal;import java.math.BigInteger;import java.util.Scanner;public class Main {	public static void main(String []args)throws Exception{		Scanner cin = new Scanner(System.in);		while(cin.hasNext()){		String a=cin.next();		String b=cin.next();		if(a.equals("0")&&b.equals("0"))			break;		BigInteger c = new BigInteger(a);		BigInteger d = new BigInteger(b);		int sum=fibo(c,d);		System.out.println(sum);		}		cin.close();	}	public static int fibo(BigInteger a,BigInteger b){		int sum =0;		BigInteger f = new BigInteger("1");		BigInteger s = new BigInteger("2");		while(true){						if(f.compareTo(b)>0)				break;			if(f.compareTo(a)>=0)				sum++;			BigInteger tem = f;			f=s;			s=s.add(tem);		}		return sum;	}}