pku2132.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define size 25

int path[size][size];
int visit[size];
int N;
int ans[201];

int GCD(int x, int y)
{
	if (y == 0)
	{
		return x;
	}
	return GCD(y, x % y);
}

int Rem(int v)
{
	int i, tmp;
	tmp = 0;
	for (i = 200; i >= 0; i--)
	{
		tmp = tmp * 10 + ans[i];
		tmp %= v;
	}
	return tmp;
}

void mult(int v)
{
	int i;

	for (i = 0; i < 201; i++)
	{
		ans[i] *= v;
	}
	for (i = 0; i < 200; i++)
	{
		ans[i + 1] += ans[i] / 10;
		ans[i] %= 10;
	}
}

void DFS(int p, int v)
{
	int i;
	if (v != 0 && Rem(v) == 0)
	{
		return;
	}
	if (p == 1)
	{
		mult(v / GCD(Rem(v), v));
		return;
	}
	for (i = 0; i < N; i++)
	{
		if (!visit[i] && path[i][p])
		{
			visit[i] = 1;
			DFS(i, GCD(path[i][p], v));
			visit[i] = 0;
		}
	}
}

int main()
{
	int i, j;
	scanf("%d", &N);

	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			scanf("%d", &path[i][j]);
		}
	}

	memset(visit, 0, sizeof(visit));
	memset(ans, 0, sizeof(ans));
	ans[0] = 1;
	visit[0] = 1;
	DFS(0, 0);
	i = 200;
	while (!ans[i])
		i--;
	for (; i >= 0; i--)
	{
		printf("%d", ans[i]);
	}
	printf("\n");
}