FIBVAL – spoj

Đề bài

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

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õ

Khuyên dùng

 

Speak Your Mind

*