Cod sursa(job #78797)

Utilizator gurneySachelarie Bogdan gurney Data 19 august 2007 20:06:12
Problema Reguli Scor 90
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.23 kb
program reguli;
  const
    fin='reguli.in';
    fout='reguli.out';
  var
    a:array[1..500000] of int64;
    pi:array[1..500000] of longint;
    d,q,i,c,r,j,k,n,x,y:longint;
    t1,t2:int64;
    ok:array[1..500000] of boolean;
begin
  assign(input,fin);
    reset(input);
    readln(n);
    readln(t1,t2);
    a[1]:=t2-t1;
    for i:=3 to n do
      begin
        readln(t1);
        t1:=t1 xor t2;
        t2:=t1 xor t2;
        t1:=t1 xor t2;
        a[i-1]:=t2-t1;
      end;
    dec(n);
  close(input);
  assign(output,fout);
    rewrite(output);
    k:=0;
    pi[1]:=0;
    for q:=2 to n do
      begin
        while (k>0) and (a[k+1]<>a[q]) do
          k:=pi[k];
        if a[k+1]=a[q] then
          inc(k);
        pi[q]:=k;
      end;
    k:=n;
    while k>0 do
      begin
        ok[pi[k]]:=true;
        k:=pi[k];
      end;
    for d:=1 to n do
      begin
        r:=n mod d;
        c:=n div d;
        if (n-r-pi[n-r]<>0)and(ok[r]) then
          if ((n-r) mod (n-r-pi[n-r])=0)and((n-r)div(n-r-pi[n-r])=c) then
            begin
              writeln(d);
              for i:=1 to d do
                writeln(a[i]);
              break;
            end;
      end;
  close(output);
end.