Program poj2132;//By_Thispoet
Const 	
	maxn=25;
Type	
	arr				=array[0..310]of Integer;
Var
	i,j,k,m,n,p		:Longint;
	map				:Array[1..maxn,1..maxn]of Longint;
	v				:Array[1..maxn]of Boolean;
	prime			:Array[1..2000]of Boolean;
	List,num,now	:Array[0..310]of Integer;
	tmp				:Array[1..2000,0..310]of Integer;
	ans				:Int64;

Function Min(i,j:Longint):Longint;
begin
	if i<j then exit(i);exit(j);
end;


Function Max(i,j:Longint):Longint;
begin
	if i>j then exit(i);exit(j);
end;
	

Procedure Prime_Prepare;
begin
	fillchar(prime,sizeof(prime),1);
	fillchar(list,sizeof(list),0);
	for i:=2 to 2000 do
		if prime[i] then
			begin
				inc(list[0]);
				list[list[0]]:=i;
				m:=i*2;
				while m<=2000 do
					begin
						prime[m]:=false;
						inc(m,i);
					end;
			end;
	fillchar(tmp,sizeof(tmp),0);
	for j:=1 to 2000 do
		begin
			i:=j;
			for k:=1 to list[0] do
				begin
					if (i mod list[k]=0) then
						begin
							p:=0;
							repeat
								inc(p);
								i:=i div list[k];
							until i mod list[k]<>0;
							tmp[j,k]:=p;
						end;
					if i=1 then break;
				end;
		end;
end;


Procedure Union(now:arr);
var i:Longint;
begin
	for i:=1 to list[0] do
		num[i]:=Max(num[i],now[i]);
end;


Procedure Insert_Gcd(i:Longint;var now:arr);
var j,p:Longint;
begin
	for j:=1 to list[0] do
		if now[j]<>-1 then now[j]:=Min(now[j],tmp[i,j]) else now[j]:=tmp[i,j];
end;


Function Check(TNode:Arr):Boolean;
var i:Longint;
begin
	for i:=1 to list[0] do
		if TNode[i]>num[i] then exit(false);
	exit(true);
end;


Procedure Dfs(i:Longint;now:arr);
var j:Longint;
	Tnode:arr;
begin
	if i=2 then
		begin
			Union(now);
			exit;
		end;
	for j:=2 to n do
		if (not v[j])and(map[i,j]>0) then
			begin
				TNode:=now;
				Insert_Gcd(map[i,j],TNode);
				if check(TNode) then continue;
				v[j]:=true;
				Dfs(j,TNode);
				v[j]:=false;
			end;
end;


BEGIN


	Prime_prepare;
	readln(n);
	for i:=1 to n do for j:=1 to n do read(map[i,j]);
	v[1]:=true;
	fillchar(now,sizeof(now),255);
	Dfs(1,now);
	ans:=1;
	for i:=1 to list[0] do
		for j:=1 to num[i] do ans:=ans*list[i];
	writeln(ans);


END.

• Re:Dfs水题…… (2466) whybert 2012-11-16 00:11:25
  • Re:Dfs水题…… (914) whybert 2012-11-16 00:11:42