UVA 10183 - How Many Fibs?

#include<bits/stdc++.h>
// #include <iostream>
// #include <cstdio>
// #include <cstdlib>
// #include <algorithm>
// #include <cmath>
// #include <vector>
// #include <set>
// #include <map>
// #include <queue>
// #include <ctime>
// #include <cassert>
// #include <complex>
// #include <string>
// #include <cstring>
// #include <queue>
// #include <bitset>

using namespace std;
typedef long long           ll;
typedef unsigned long long  ull;

#define ff                  first
#define ss                  second
#define pb                  push_back
#define mp                  make_pair
#define in                  insert
#define vi                  vector< int >
#define vll                 vector< ll >


#define f0(b)               for(int i=0;i<(b);i++)
#define f00(b)              for(int j=0;j<(b);j++)
#define f1(b)               for(int i=1;i<=(b);i++)
#define f11(b)              for(int j=1;j<=(b);j++)
#define f2(a,b)             for(int i=(a);i<=(b);i++)
#define f22(a,b)            for(int j=(a);j<=(b);j++)
#define RFOR(i,x,y)         for(int i=x;i>=y;i--)
#define unq(v)              sort(all(v)),(v).resize(unique(all(v))-v.begin())
#define all(v)              v.begin(),v.end()
#define rall(v)             v.rbegin(),v.rend()
#define reversed(s)         reverse(s.begin(), s.end())

#define testcase            ll t; cin>>t; while (t--)
#define vout(v)             for(int ind=0;ind<v.size();ind++){ cout<<v[ind]; if(ind<v.size()-1) cout<<' '; else cout<<endl;}
#define arrout(arr,i,x,y)   for(int i=x;i<=y;i++){ cout<<arr[i]; if(i<y) cout<<' '; else cout<<endl;}
#define READ()              freopen("input.txt", "r", stdin)
#define WRITE()             freopen("output.txt", "w", stdout)

#define sci(n)              scanf("%d",&n)
#define scii(x,y)           scanf("%d %d",&x,&y)


#define scl(n)              scanf("%lld",&n)
#define scll(x,y)           scanf("%lld %lld",&x,&y)
#define gtl(x)              getline(cin, (x))

#define PI                  acos(-1)
#define CLR(x, y)           memset(x, y, sizeof(x))
#define Precision(a)        cout << fixed << setprecision(a)
#define Flame()             ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define MAXP                10000
#define MOD                 1e9+7//10000007
#define EPS                 1e-7

template <typename T> T Sqr(T x)
{
    T n = x * x ;
    return n ;
}
template <typename T> T Pow(T B,T P)
{
    if(P==0) return 1;
    if(P&1) return B*Pow(B,P-1);
    else return Sqr(Pow(B,P/2));
}
template <typename T> T Abs(T a)
{
    if(a<0)return -a;
    else return a;
}
template <typename T> T Gcd(T a,T b)
{
    if(a<0)return Gcd(-a,b);
    if(b<0)return Gcd(a,-b);
    return (b==0)?a:Gcd(b,a%b);
}
template <typename T> T Lcm(T a,T b)
{
    if(a<0)return Lcm(-a,b);
    if(b<0)return Lcm(a,-b);
    return a*(b/Gcd(a,b));
}
template <typename T> T BigMod (T b,T p,T m)
{
    if (p == 0) return 1;
    if (p%2 == 0)
    {
        T s = BigMod(b,p/2,m);
        return ((s%m)*(s%m))%m;
    }
    return ((b%m)*(BigMod(b,p-1,m)%m))%m;
}
template <typename T> inline string ToBinary(T n)
{
    string r ;
    while(n != 0)
    {
        r = ( n % 2 == 0 ? "0" : "1" ) + r ;
        n >>= 1;
    }
    return r ;
}
long long BinaryToDecimal(string s)
{
    int len = s.size();
    long long n = 0, p = 1;
    for (int i = len - 1; i >= 0; i--, p *= 2) n += p * (s[i] - '0');
    return n;
}

int Strtoint(string str)
{
    stringstream ss(str);
    int x = 0;
    ss >> x ;
    return x ;
}
string Intostr(int x)
{
    stringstream ss;
    ss << x;
    string str = ss.str();
    return str;
}

#define bug printf("**!\n")
#define D(x)            cerr << __LINE__ << ": " #x " = " << (x) << '\n'
#define DD(x, y)        cerr << __LINE__ << ": " #x " = " << (x) << ", " #y " = " << (y) << '\n'
#define DDD(x, y, z)    cerr << __LINE__ << ": " #x " = " << (x) << ", " #y " = " << (y) << ",  " #z " = " << (z) << '\n'
string fib[MAXP];
string Add_sum(string str1,string str2)
{

    if (str1.length() > str2.length())
        swap(str1, str2);


    int n1 = str1.length(), n2 = str2.length();
    string str = "";

    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
    ll carry = 0;
    for (int i=0; i<n1; i++)
    {
        // Do school mathematics, compute sum of
        // current digits and carry
        int sum = ((str1[i]-'0')+(str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');

        // Calculate carry for next step
        carry = sum/10;
    }

    // Add remaining digits of larger number
    for (int i=n1; i<n2; i++)
    {
        int sum = ((str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');
        carry = sum/10;
    }

    // Add remaining carry
    if (carry)
        str.push_back(carry+'0');

    // reverse resultant string
    reverse(str.begin(), str.end());

    return str;
}

void Fibs()
{
    fib[0]="0";
    fib[1]="1";
    for(ll i=2; i<=1000; i++)
    {
        fib[i]=Add_sum(fib[i-1], fib[i-2]);
    }
}

bool ckr1(string a, string b)
{
    if(a.length()!=b.length())
    {
        if(a.length()>b.length()) return 1;
        else return 0;
    }
    for(ll i=0; i<a.length(); i++)
    {
        if(a[i]!=b[i])
        {
            if(a[i]>b[i]) return 1;
            else return 0;
        }
    }
    return 1;
}
bool ckr2(string a, string b)
{
    if(a.length()!=b.length())
    {
        if(a.length()>b.length()) return 0;
        else return 1;
    }
    for(ll i=0; i<a.length(); i++)
    {
        if(a[i]!=b[i])
        {
            if(a[i]>b[i]) return 0;
            else return 1;
        }
    }
    return 1;
}
int main()
{
    Flame();
    Fibs();
    string a,b;
    while(cin>>a>>b)
    {
        if(a=="0" && b=="0") break;
        ll cnt=0;
        for(ll i=2; i<=1000; i++)
        {
            if(ckr1(fib[i],a) && ckr2(fib[i],b))
            {
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}