FIBVAL – spoj

Đề bài

• http://vn.spoj.com/problems/FIBVAL/

Thuật toán

Để giải được bài này, ta cần áp dụng 1 tính chất đặc biệt của dãy Fibonacci, đó là chu kỳ Pisano

Dãy Fibonacci có dạng:

• f(0) = 0
• f(1)=1
• f(i)=f(i-1)+f(i-2)

Đối với 1 số nguyên n bất kì thì dãy g(i)=f(i) mod n có tính chu kì.

Ví dụ: Với n=3 ta có:

f	0	1	1	2	3	5	8	13	15	28	43	…
g	0	1	1	2	0	2	2	1	0	1	1	…

Ở bài này, ta có chu kì gồm 7 nốt nhạc vì vậy ta xét tính chu kì trên dãy g(i)=f(i) mod 7.

Chu kì Peisano của 7 trong bài này gồm 16 số:

 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1

Như vậy, độ dài đoạn nhạc dài nhất có tính chu kì chỉ có thể là 2 hoặc có dạng 16*k.

Code

• Pascal

CONST
    tfi = '';
    tfo = '';
VAR
    fi,fo           : text;

Function pro(l,r: longint): longint;
    Var
        len,res: longint;
    Begin
        len:=r-l+1;
        l:=l mod 16;
        r:=r mod 16;
        If l=0 then l:=16;
        If r=0 then r:=16;
        res:=len div 16;
        If len>=32 then exit(res*16)
        else
            If len>=9 then exit(2)
            else
                If ((l=9)) or ((l>9) and (r0 do
            begin
                read(fi,l,r);
                writeln(fo,pro(l,r));
                dec(test);
            end;
    End;

BEGIN
    assign(fi,tfi); reset(fi);
    assign(fo,tfo); rewrite(fo);
        process;
    close(fi); close(fo);
END.

Nguồn: không rõ