将斐波那契的前100000个，每个的前40位都插入到字典树里（其他位数删掉），然后直接查询字典树就行。
此题坑点在于
1、字典树的深度不能太大，事实上，超过40在hdu就会MLE……
2、若大数加法时，保存的位数过少，就会导致低位误差，累积起来就可能导致前40位产生错误，解决办法是提高精度。
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
struct Trie
{
struct Trie *son[10];
int id;
}*root;
void insert(char s[],int ID)
{
int i,j;
struct Trie *c,*newnode;
c=root;
for(i=0;s[i];i++)
{
if(c->son[s[i]-'0'])
{
c=c->son[s[i]-'0'];
}
else
{
c->son[s[i]-'0']=new Trie;
for(j=0;j<10;j++) c->son[s[i]-'0']->son[j]=0;
c=c->son[s[i]-'0'];
c->id=ID;
}
}
}
int find(char *s)
{
int i;
int len;
struct Trie *c;
len=strlen(s);
if(len==0) return 0;
c=root;
for(i=0;i<len;i++)
{
if(c->son[s[i]-'0']!=0)
{
c=c->son[s[i]-'0'];
}
else
return -1;
}
return c->id;
}
void init()
{
root=new Trie;
for(int i=0;i<10;i++) root->son[i]=0;
}
char a[60]="1",b[60]="1",c[60];
int main()
{
char str[50];
int cas;
int ca=1;
init();
insert("1",0);
int la=1;
int lb=1;
for(int i=2;i<100000;i++)
{
int len=max(la,lb);
int x=0;
int top=0;
for(int j=0;j<len;j++)
{
if(j>=la) a[j]='0';
int s=x+a[j]+b[j]-2*'0';
x=s/10;
c[top++]=s%10+'0';
}
if(x) c[top++]=x+'0';
c[top]=' ';
if(top>50) //计算数列的精度必须大一些
{
for(int j=0;j<49;j++) a[j]=b[j+1];a[la=49]=' ';
for(int j=0;j<50;j++) b[j]=c[j+1];
b[lb=50]=' ';
}
else
{
la=lb;
strcpy(a,b);
strcpy(b,c);
lb=top;
}
int j,c;
for(j=lb-1,c=0;j>=0&&c<40;c++,j--) str[c]=b[j];str[c]=' ';//字典树的深度绝对不能太大，超过40就要MLE！
insert(str,i);
}
// cout<<"ok"<<endl;
cin>>cas;
while(cas--)
{
scanf("%s",str);
printf("Case #%d: %d
",ca++,find(str));
}
return 0;
}