题目大意：

我们按以下方式产生序列：

1、 开始时序列是： “1” ；

2、 每一次变化把序列中的 “1” 变成 “10” ，”0” 变成 “1”。

经过无限次变化，我们得到序列”1011010110110101101…”。

然后询问Q次，求a到b之间1的个数——

解题思路：

首先，观察一波 —— 序列的变化为：

1

10

101

10110

10110101

然后，我们发现Si（第i次变化）=S(i-1)+S(i-2)

就是斐波那契——

然后可以用递归的方法求出从位置1到位置X之间所有的1的个数。

源程序:

#include 
    
     #include 
     
      #define r(i,a,b) for(int i=a;i<=b;i++)using namespace std;unsigned long long f[93],f1[93],a,b;int l,ll,n;void ycl(){    f[0]=f[1]=f1[1]=1;    f1[0]=0;    r(i,2,92)     {        f[i]=f[i-1]+f[i-2];        f1[i]=f1[i-1]+f1[i-2];     }}unsigned long long find(unsigned long long a,unsigned long long b)//递归{    if (!a) return 0;    if (a==f[b]) return f1[b];    else if(a<=f1[b]) return find(a,b-1);    else return f1[b-1]+find(a-f[b-1],b-2);}int main(){    ycl();//斐波那契序列    scanf("%d",&n);    for (int i=1;i<=n;i++)    {        cin>>a>>b;        //不知道为什么scanf("%llu%llu",&a,&b);不行        //所以就用cin        cout<
      
       <