www.pudn.com > TJU.rar > ac1084.pas

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 e0 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.