hdu 1316 How many Fibs高精度斐波那契数

//  大数继续

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 addstring x,string y)
{
    string ans ;
    int lenx = x.length);
    int leny = y.length);
    iflenx<leny)
    {
        forint i = 1;i<=leny-lenx;i++)
            x = "0"+x;
    }
    else
    {
        forint i = 1;i<=lenx-leny;i++)
            y = "0"+y;
    }
    lenx = x.length);
    int cf = 0;
    int temp;
    forint i = lenx-1;i>=0;i--)
    {
        temp = x[i] - '0' + y[i] - '0'+cf;
        cf = temp/10;
        temp%=10;
        ans = char'0'+temp)+ans;
    }
    ifcf!=0)
        ans = charcf+'0')+ans;
    return ans;
}
int comparestring x,string y)//  字符串形式的数的比较大小
{
    int i,lenx = x.length),leny = y.length),leaf;
    ifx==y)  return 0;//   0 表示 x == y
    ifx.length)>y.length))   return 1;// 返回1 表示 x > y
    ifx.length)<y.length))   return -1;// -1 表示 x < y
    ifx.length)==y.length))
    {
        fori = 0;i<lenx;i++)
        {
            ifx[i]==y[i])  continue;
            ifx[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";
    forint i = 3;i<=1000;i++)
        num[i] = addnum[i-1],num[i-2]);
    whilecin>>x>>y&&x!="0"||y!="0")//  x y 均为 0 的时候才结束程序
    {
        ify == "0")//  y == 0  时 直接输出 0
         {
            printf"0");
            continue;
        }
        start = eend = 0;
        /**
        j = k = 0;
        whilex[j]=='0')//  受到
            j++;
        x = x.substrj,x.length)-j);//  受到 hdu 1753 的影响，以为会有前导0，其实没有

        whiley[k]=='0')
            k++;
        y = y.substrk,y.length)-k);
        **/
        fori = 1;i<1000;i++)
        {
            ifcomparex,num[i])==0)
            {
                start = i;
                break;
            }
            else ifcomparenum[i],x)==-1&&comparenum[i+1],x)==1)
            {
                start = i+1;
                break;
            }
        }
        fori = 1;i<1000;i++)
        {
            ifcomparey,num[i])==0){
                eend = i;break;
            }
            else ifcomparenum[i],y)==-1&&comparenum[i+1],y)==1){
                eend = i;break;
            }
        }
        ifx=="0") //  注意  x == 0 时的情况
            start = 1;
        //cout<<start<<"      "<<eend<<endl;;
        cout<<eend-start+1<<endl;
    }
}