记录编号	32937	评测结果	AAAAAAAAAA
题目名称	607.产生01串	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.106 s
提交时间	2011-11-08 20:08:28	内存使用	0.27 MiB

#include<iostream>  
#include<fstream>  
  
using namespace std;  
  
int n;  
unsigned long long a,b,ans,f[94],g[94];  
  
void fibonacci()  
{  
    int i;  
    f[1]=1;  
    f[2]=2;  
    g[1]=1;  
    g[2]=1;  
    for(i=3;i<93;i++)  
    {  
        f[i]=f[i-1]+f[i-2];  
        g[i]=g[i-1]+g[i-2];  
    }  
}  
  
unsigned long long work(unsigned long long a,int i)  
{  
    unsigned long long sum;  
    if(a==0)  
        return 0;  
    if(a==f[i])  
        return g[i];  
    if(a<=f[i])  
        return work(a,i-1);  
    else  
    {  
        sum=work(a-f[i],i-2);  
        return g[i]+sum;  
    }  
}  
  
int main()  
{  
    int i;  
    ifstream fin("infinit.in");  
    ofstream fout("infinit.out");  
    fibonacci();  
    fin>>n;  
    for(i=1;i<=n;i++)  
    {  
        fin>>a>>b;  
        ans=work(b,92)-work(a-1,92);  
        fout<<ans<<endl;  
    }  
    fin.close();  
    fout.close();  
    return 0;  
}