SPOJ #536. How many Fibs

时间:2022-08-14 23:10:16

Since number could be 10^100, we have to use large number processing method, in string. A simpler method is to pre-calculate all Fibonacci numbers up to 101 digits, which is already fast enough.

//

#include <vector>
#include <iostream>
#include <string>
#include <cmath>
using namespace std; vector<string> dict; string plus_str(string &a, string &b)
{
unsigned sizeA = a.length();
unsigned sizeB = b.length();
unsigned sizeDlt = (unsigned)abs(float(sizeA - sizeB)); string &sL = sizeA > sizeB ? a : b;
string &sS = !(sizeA > sizeB) ? a : b; unsigned sizeL = max(sizeA, sizeB);
string ret(sizeL + , ''); int carry = ;
for(int i = sizeL - ; i >= ; i --)
{
int inxL = i;
int inxS = i - sizeDlt;
int inxR = i + ; int dL = sL[inxL] - '';
int dS = inxS < ? : sS[inxS] - ''; int sum = dL + dS + carry;
ret[inxR] = sum % +'';
carry = sum >= ? : ;
} if(carry)
{
ret[] = '';
}
else
{
ret.erase(, );
}
return ret;
} // 1 : a > b
// -1: a < b
// 0 : a == b
//
int comp(string &a, string &b)
{
unsigned sza = a.size();
unsigned szb = b.size();
if(sza != szb) return sza > szb ? : -; // the same length
for(unsigned i = ; i < sza; i ++)
{
int da = a[i] - '';
int db = b[i] - '';
if(da != db)
{
return da > db ? : -;
}
}
return ; // equal
} void fill_fib(vector<string> &dict)
{
dict.push_back("");
dict.push_back(""); bool bBreak = false;
int i = ;
while(!bBreak)
{
string newFib = plus_str(dict[i - ], dict[i - ]);
dict.push_back(newFib);
bBreak = newFib.length() >= ;
i ++;
}
} int get_fib_cnt(string &a, string &b)
{
int ret = ; unsigned nSize = dict.size();
for(int i = ; i <nSize; i ++)
{
if(comp(dict[i], b) == ) break;
if(comp(dict[i], a) >= )
{
cout << "Found " << dict[i] << endl;
ret ++;
}
} return ret;
} int main()
{ fill_fib(dict); string a, b;
cin >> a >> b; while(!(a == "" && b == ""))
{
cout << get_fib_cnt(a, b) << endl;
cin >> a >> b;
} return ;
}

I tried to find a closed form to Fibonacci only after I got a 0.01sec AC:
http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression