邻接表强迫症 欧拉筛强迫症 各种强迫症...

program usaco2003cowmath;

type tnode=record
        n,w,dw,next:longint;
     end;
     bigint=array[0..117] of longint;

const maxw=2017;
      maxn=26;
      maxm=2017;
      base=10000;

var g,q:array[1..maxn] of longint;
    v:array[1..maxn] of boolean;
    p:array[1..maxw] of boolean;
    prime:array[1..maxw] of longint;
    mem:array[1..maxm] of tnode;
    cp,n,memsize,maxe,maxd:longint;

function max(i,j:longint):longint; begin
if i>j then exit(i) else exit(j);  end;

procedure sieve(n:longint);
var i,j:longint;
begin
fillchar(p,sizeof(p),true);
cp:=0; p[1]:=false;
for i:=1 to n do begin
        if p[i] then begin
                inc(cp); prime[cp]:=i;
        end;
        for j:=1 to cp do if i*prime[j]<=n then begin
                p[i*prime[j]]:=false;
                if i mod prime[j] = 0 then break;
        end else break;
end;
end;

function exp(a,n:int64):int64;
var t:int64;
begin
exp:=1; t:=a;
while n>0 do begin
        if n and 1 = 1 then exp:=exp*t;
        t:=t*t;
        n:=n>>1;
end;
end;

procedure insnbs(u,v,iw:longint);
begin
inc(memsize); with mem[memsize] do begin
        n:=v; w:=iw; next:=g[u];
end; g[u]:=memsize; maxd:=max(maxd,iw);
end;

function reweight(n:longint):longint;
var i,j:longint;
begin
reweight:=0;
for i:=1 to memsize do begin
        mem[i].dw:=0; j:=mem[i].w;
        while j mod n = 0 do begin
                inc(mem[i].dw); j:=j div n;
        end;
        reweight:=max(reweight,mem[i].dw);
end;
end;

function connect(lim:longint):boolean;
var head,tail,i,j,frt,rer,t1:longint;
begin
fillchar(v,sizeof(v),0);
frt:=0; rer:=1;
q[1]:=1; v[1]:=true;
while frt<rer do begin
        inc(frt); head:=q[frt]; t1:=g[head];
        while t1<>0 do begin
                tail:=mem[t1].n;
                if (not v[tail])and(mem[t1].dw>=lim) then begin
                        if tail=2 then exit(true);
                        v[tail]:=true; inc(rer); q[rer]:=tail;
                end;
                t1:=mem[t1].next;
        end;
end;
exit(false);
end;

function binfind(n:longint):longint;
var l,r,mid:longint;
begin
l:=0; r:=maxe;
while l<>r do begin
        mid:=(l+r)>>1;
        if connect(mid+1) then l:=mid+1 else r:=mid;
end;
exit(l);
end;

procedure init;
var i,j,k:longint;
begin
readln(n);
for i:=1 to n do
        for j:=1 to n do begin
                read(k);
                if k<>0 then insnbs(i,j,k);
        end;
end;

function one:bigint;
begin
fillchar(one,sizeof(one),0);
one[0]:=1; one[1]:=1;
end;

function mul(a:bigint;b:longint):bigint;
var i:longint;
begin
fillchar(mul,sizeof(mul),0);
mul[0]:=a[0];
for i:=1 to a[0]-1 do begin
        inc(mul[i],a[i]*b);
        inc(mul[i+1],mul[i] div base);
        mul[i]:=mul[i] mod base;
end; inc(mul[a[0]],a[a[0]]*b);
while mul[mul[0]]>=base do begin
        inc(mul[mul[0]+1],mul[mul[0]] div base);
        mul[mul[0]]:=mul[mul[0]] mod base;
        inc(mul[0]);
end;
end;

function ans:bigint;
var i,j,k:longint;
begin
ans:=one;
for i:=1 to cp do begin
        maxe:=reweight(prime[i]);
        ans:=mul(ans,exp(prime[i],binfind(prime[i])));
end;
end;

procedure print(a:bigint);
const initstr='0000';
var i,j:longint;
    str:string;
begin
write(a[a[0]]);
for i:=a[0]-1 downto 1 do begin
        str:=initstr; j:=5;
        while a[i]>0 do begin
                dec(j); str[j]:=chr(a[i] mod 10+48);
                a[i]:=a[i] div 10;
        end; write(str);
end; writeln;
end;

begin
init;
sieve(maxd);
print(ans);
end.