Một đôi thỏ (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con
(cũng gồm một thỏ đực và thỏ cái); một đôi thỏ con, khi tròn 2 tháng tuổi, sau mỗi tháng đẻ
ra một đôi thỏ con, và quá trình sinh cứ thế tiếp diễn. Hỏi n tháng có bao nhiêu đôi thỏ, nếu
đầu năm có một đôi thỏ sơ sinh? Đó là câu chuyện vui về số Fibonaci, số này được định nghĩa
như sau:
– f(0) = 0.
– f(2) = f(1) = 1.
– f(n)= f(n-1) +f(n-2) với n > 2.
Yêu cầu: Cho hai số nguyên dương A và B, Tính số lượng số Fibonaci có giá trị trong
đoạn [A..B].
Dữ liệu vào: từ tập tin văn bản CFIBO.INP gồm hai số nguyên dương A và B cách
nhau ít nhất một khoảng trắng (0 ≤ A ≤ B ≤ 2*10^10).
Kết quả: ghi ra tập tin văn bản CFIBO.OUT một số nguyên duy nhất là số lượng số
Fibonaci có giá trị trong đoạn [A..B].
const fi=’cfibo.inp’;
fo=’cfibo.out’;
maxn=round(1e8);
var m,n,d:qword;
i:longint;
a: array [0..maxn] of int64;
b: array [0..maxn] of boolean;
procedure ganfibo;
begin
fillchar(b,sizeof(d),false);
a[0]:=0;
a[1]:=1;
for i:= 2 to n do a[i]:=a[i-1]+a[i-2];
for i:=0 to n do
b[a[i]]:=true;
end;
begin
assign(input,fi);
reset(input);
read(m,n);
close(input);
ganfibo;
for i:=m to n do
if b[i] then inc(d);
assign(output,fo);
rewrite(output);
write(d);
close(output);
end.