2136. The good old fibonacci.

AC代码来一发

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

using namespace std;

const int maxn = 500;

string f[maxn];

string add(string s1, string s2)
{
string f1 = “”, f2 = “”, s = “”;
for (int i = s1.size()-1; i >= 0; –i)
f1.push_back(s1[i]);
for (int i = s2.size()-1; i >= 0; –i)
f2.push_back(s2[i]);
int re = 0;
int len = max(f1.size(), f2.size());
for (int i = 0; i < len; ++i)
if (i >= f1.size())
{
s.push_back((f2[i]-‘0’+re)%10+‘0’);
re = (f2[i]- ‘0’ + re) / 10;
}
else
if (i >= f2.size())
{
s.push_back((f1[i]-‘0’+re)%10+‘0’);
re = (f1[i]- ‘0’ + re) / 10;
}
else
{
s.push_back((f1[i]+f2[i]-2*‘0’+re)%10+‘0’);
re = (f1[i] + f2[i] - 2 * ‘0’ + re) / 10;
}
if (re)
{
s.push_back(re+‘0’);
len++;
}
for (int i = 0; i < (len>>1); ++i)
swap(s[i], s[len-1-i]);
return s;
}

void init()
{
f[0] = “1”;
f[1] = “2”;
for (int i = 2; i < maxn; ++i)
f[i] = add(f[i-1], f[i-2]);
}

bool cmp(string s1, string s2)
{
if (s1.size() != s2.size())
return s1.size() >= s2.size();
return s1 >= s2;
}

int main()
{
init();
string a, b;
while (cin >> a >> b)
{
if (a == “0” && b == “0”)
break;
int l, r;
for (l = 0; l < maxn; ++l)
if (cmp(f[l], a))
break;
for (r = maxn-1; r >= 0; –r)
if (!cmp(f[r], b) || f[r] == b)
break;
printf(“%d\n”, r-l+1);
}
return 0;
}