Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 顺便该算法+高精度P代码

Posted by Hoblovski at 2014-03-29 21:33:12 on Problem 2132
In Reply To:题解 + 强数据 (数据太弱太弱) Posted by:Hoblovski at 2014-03-29 21:32:00
```邻接表强迫症 欧拉筛强迫症 各种强迫症...

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;
begin
fillchar(v,sizeof(v),0);
frt:=0; rer:=1;
q[1]:=1; v[1]:=true;
while frt<rer do begin
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
for i:=1 to n do
for j:=1 to n do begin
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.
```

Followed by: