一道Pascal题目：牛牛看到了一个非常有意思的游戏：游戏一开始，电脑屏幕上只有一个序列“A”，而后的每一次变化都把序列中的“A”变成“AB”，“B”变成“A”。游戏一直继续……，最

Question

一道Pascal题目：
牛牛看到了一个非常有意思的游戏：游戏一开始，电脑屏幕上只有一个序列“A”，而后的每一次变化都把序列中的“A”变成“AB”，“B”变成“A”。游戏一直继续……，最后屏幕上得到了序列“ABAABABAABAABABAABA……”。当然更有意思的是，电脑会提出Q个询问，每次询问：在第m个字符和第n个字符之间有多少个有多少个“A”（包括第m、n个字符在内）。你能帮牛牛解决这个问题吗？

Answer 1

1. 放程序题要放完整题目描述，m,n范围，完整输入输出格式好么亲=.=!

2. 这个实际效果类似于生成斐波那契数列，实现通过计算前m个里面的减去前n-1里面的

3. n,m会比较大小；n,m不要超过斐波那契数列第86项：420196140727489673

var
 n, m, temp:int64;
 i, q:integer;
 f, len:array [0..100] of int64;
//how many a in first p
function get(p:int64):int64;
var
 ii,a:integer;
 b, ans:int64;
begin
 if p<=0 then exit(0);
 a:=85;
 b:=p;
 ans:=0;
 while (a>2) do
  if b>len[a-1] then
  begin
   b:=b-len[a-1];
   ans:=ans+f[a-1];
   a:=a-2;
  end else
   a:=a-1;
 exit(ans+1);
end;
begin
 //preparation
 f[1]:=1; len[1]:=1;
 f[2]:=1; len[2]:=2;
 for i:=3 to 85 do
 begin
  f[i]:=f[i-1] + f[i-2];
  len[i]:=len[i-1] + len[i-2];
 end;

 //read and solve
 readln(q);
 for i:=1 to q do
 begin
         readln(n,m);
  if (m<n) then
  begin
   temp:=m; m:=n; n:=temp;
  end;
         writeln(get(m) - get(n-1));
 end;
end.