ac1164.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1164;
const
  maxn=1000;
  base=10000;
type
  bignum=array[-1..751]of longint;
var
  a,b:bignum;
  n,m:word;
procedure square(var a,b:bignum);
  var
    i,j,k:word;
  begin
    fillchar(b,sizeof(b),0);
    for i:=0 to a[-1] do
      for j:=0 to a[-1] do begin
        k:=i+j;
        inc(b[k],a[i]*a[j]);
        inc(b[k+1],b[k] div base);
        b[k]:=b[k] mod base;
      end;
    b[-1]:=a[-1]*2;if b[b[-1]+1]>0 then inc(b[-1]);
  end;
procedure mul(var a:bignum);
  var
    i:word;
  begin
    for i:=0 to a[-1] do
      a[i]:=a[i]*m;
    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 calpower(p:word;var a,b:bignum);
  begin
    if p=1 then begin
      a[-1]:=0;a[0]:=m
    end
    else begin
      calpower(p shr 1,b,a);
      square(b,a);
      if odd(p) then mul(a);
    end;
  end;
procedure reduce(var a:bignum);
  var
    i:word;
  begin
    dec(a[0],n-1);
    i:=0;while a[i]<0 do begin inc(a[i],base);inc(i);dec(a[i],1);end;
    while a[a[-1]]=0 do dec(a[-1]);
  end;
procedure out;
  var
    i:integer;
  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);
  end;
begin
  repeat
    read(n);
    m:=n;calpower(n,a,b);reduce(a);out;write(' ');
    m:=n-1;calpower(n,a,b);reduce(a);out;writeln;
  until seekeof;
end.