2132.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
int a[700],n,st;
int map[26][26];
bool sign[26];
int num[2000],len;
void cheng(int a)
{int i,t;
for(i=0,t=0;i<len;i++)
{num[i]*=a;num[i]+=t;
t=num[i]/10;
num[i]%=10;
}
while(t)
{num[len++]=t%10;
t/=10;
}

}
bool find(int s,int g)
{
	int i;
	if(s==1)return 1;
	sign[s]=0;
	for(i=0;i<n;i++)
		if(sign[i]&&map[s][i]&&map[s][i]%g==0)
		{
			if(find(i,g))return 1;
		}
	return 0;
}
int gcd(int a,int b)
{
	int c;
	while(a%b)
	{
		c=b;
		b=a%b;
		a=c;
	}
	return b;
}
int main()
{
	int i,j,k,g,h;
	cin>>n;
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	{
		cin>>map[i][j];
	}	
	st=0;
	for(i=1;i<2001;i++)
	{
		for(j=0;j<n;j++)sign[j]=1;
		
		if(find(0,i))
		{
			h=i;
			for(k=0;k<st&&h>1;k++)
				if((g=gcd(h,a[k]))>1)
				{
					h/=g;
				}
			if(k==st)a[st++]=h;
		}
	}	
	num[0]=1;
	len=1;
	for(i=0;i<st;i++)
		cheng(a[i]);
	for(i=len-1;i>=0;i--)
		cout<<num[i];
	
	cout<<endl;

	return 0;
}