记录编号	92683	评测结果	AAAWAAAAWA
题目名称	考验	最终得分	80
用户昵称	醉江楼	是否通过	未通过
代码语言	C++	运行时间	0.007 s
提交时间	2014-03-21 23:07:54	内存使用	0.30 MiB

#include<stdio.h>

#define MAXN 30

int n,m,k=1,map[MAXN][MAXN];

int use[MAXN];

int gcd(int a,int b)
{
	if (a==0) return b;

	int r=a%b;
	
	while (r)
	{
	a=b;
	b=r;
	r=a%b;
	}

	return b;
}

int gcc(int a,int b)
{
	if (a==0) return b;

	int x=a,y=b,r=a%b;
	
	while (r)
	{
	a=b;
	b=r;
	r=a%b;
	}

	return x*y/b;
}

void dfs(int x,int m)
{
	if (m&&k&&k%m==0) return ;
	if (x==2) {
		k=gcc(k,m);
		return ;
	}

	use[x]=1;
	for (int i=1;i<=n;++i)
		if (map[x][i]&&!use[i])
		{
		dfs(i,gcd(m,map[x][i]));
		use[i]=0;
		}
}

int main()
{
	int i,j;

	freopen("testz.in","r",stdin);
	freopen("testz.out","w",stdout);

	scanf("%d",&n);

	for (i=1;i<=n;++i)
		for (j=1;j<=n;++j)
			scanf("%d",&map[i][j]);

	dfs(1,0);

	printf("%d\n",k);

	return 0;
}