ac1281.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

program tju1281;
{$Q-,R-}
const
  base=10000;
type
  bignum=array[-1..2000]of longint;
var
  a,b:bignum;
  n:longint;
procedure hi_sqr(var a,b:bignum);
  var
    i,j:longint;
  begin
    fillchar(b,sizeof(b),0);
    for i:=0 to a[-1] do
      for j:=0 to a[-1] do begin
        inc(b[i+j],a[i]*a[j]);
        inc(b[i+j+1],b[i+j] div base);
        b[i+j]:=b[i+j] mod base;
      end;
    i:=a[-1]*2+1;
    while (b[i]>0) do begin b[i+1]:=b[i] div base;b[i]:=b[i] mod base;inc(i);end;
    b[-1]:=i-1;
  end;
procedure mul(var a:bignum;b:longint);
  var
    i:longint;
  begin
    for i:=0 to a[-1] do a[i]:=a[i]*b;
    for i:=0 to a[-1] do begin inc(a[i+1],a[i] div base);a[i]:=a[i] mod base;end;
    if a[a[-1]+1]>0 then inc(a[-1]);
  end;
procedure exp3(n:longint;var a,b:bignum);
  begin
    if n<9 then begin
      fillchar(a,sizeof(a),0);a[0]:=3**n;
    end
    else begin
      exp3(n div 2,b,a);
      hi_sqr(b,a);
      if odd(n) then mul(a,3);
    end;
  end;
begin
  repeat
    read(n);
    if n<5 then
      writeln(n)
    else begin
      case n mod 3 of
        0:exp3(n div 3,a,b);
        1:begin exp3((n-4) div 3,a,b);mul(a,4);end;
        2:begin exp3((n-2) div 3,a,b);mul(a,2);end;
      end;
      write(a[a[-1]]);
      for n:=a[-1]-1 downto 0 do
        write(a[n] div 1000,a[n] div 100 mod 10,a[n] div 10 mod 10,a[n] mod 10);
      writeln;
    end;
  until seekeof;
end.