ac1084.pas

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

program tju1084;
const
  primes=16;
  prime:array[1..primes]of byte=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53);
  base=10000;
type
  bignum=array[-1..7525]of longint;
var
  s,ans:array[0..primes]of longint;
  n,ansp:longint;
  anse:real;
  a,b,c,d:bignum;
  bool:boolean;
procedure search(n,p,limit:longint;e:real);
  var
    i:longint;
  begin
    if n=1 then begin
      if e<anse then begin ans:=s;anse:=e;ansp:=p;end;
      exit;
    end;
    for i:=1 to limit do
      if n mod (i+1)=0 then begin
        s[p]:=i;
        search(n div (i+1),p+1,i,e+ln(prime[p])*i);
      end;
  end;
procedure mul(var a:bignum;b:byte);
  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 hi_mul(var a,b,c:bignum);
  var
    i,j,k:longint;
  begin
    fillchar(c,sizeof(c),0);
    for i:=0 to a[-1] do
      for j:=0 to b[-1] do begin
        k:=i+j;
        inc(c[k],a[i]*b[j]);
        inc(c[k+1],c[k] div base);
        c[k]:=c[k] mod base;
      end;
    c[-1]:=a[-1]+b[-1];if c[c[-1]+1]>0 then inc(c[-1]);
  end;
procedure pow(var x,y:bignum;p:longint);
  begin
    if p=1 then begin
      fillchar(x,sizeof(x),0);x[0]:=prime[n];
    end
    else begin
      pow(y,x,p shr 1);
      hi_mul(y,y,x);
      if odd(p) then mul(x,prime[n]);
    end;
  end;
procedure out(var a:bignum);
  var
    i:longint;
  begin
    write(a[a[-1]]);
    for i:=a[-1]-1 downto 0 do
      write(a[i] div 1000,a[i] div 100 mod 10,a[i] div 10 mod 10,a[i] mod 10);
    writeln;
  end;
begin
  repeat
    read(n);
    anse:=3e38;
    search(n,1,n-1,0);
    dec(ansp);
    fillchar(a,sizeof(a),0);a[0]:=1;
    for n:=1 to ansp do begin
      pow(c,d,ans[n]);
      if odd(n) then hi_mul(a,c,b) else hi_mul(b,c,a);
    end;
    if odd(ansp) then out(b) else out(a);
  until seekeof;
end.