思路：
首先每条路径的值都可以分解一下质因数，就可以表示为多个质数的幂相乘的形式，
比如 2^6 * 3^8 * 17^22 * 23^1。
三个数字a, b, c求最大公约数，分解完质因数后：
如果a拥有2^8，b拥有2^10，c拥有2^4。那最大公约数必然拥有2^4，取最小的一个。
对于每个质数 2, 3, 5, 7。。都是这个道理。
如果是求最小公倍数，在刚刚的例子里，就是取最大的一个了。
在点之间行走的过程，可以这样来看。在点1的时候GCF的值是所有质数的最大次幂的乘积。
GCF的值必定是越走越小。
每经过一条路径，CGF各个质因数的幂都必须小于等于路径的对应的值。
就好比路径就只能容纳这么大的流量。然后到达点2的时候，看看哪条路径的流量最大。
看起来像最大流问题，但不是最大流问题。
我们没办法遍历一次图，就求出哪条路径的流量最大。
但由于路径的权值最大才2000，质因数的幂最大也只有11（2^11 = 2048），大不了每个幂都试一次。
用二分法就可以了。
对于每一个质数，求到达点2 的时候的最大的幂。
最后再乘起来，就是答案了。
可见这种方法还是很巧妙的，效率也很高，0ms AC。
注意：
不需要高精度。但需要用__int64来保存答案。
#include <stdio.h>
#define MAX_W 2048
#define MAX_N 32
int N, visit[MAX_N], map[MAX_N][MAX_N], tm;
int prime[MAX_W], prime_cnt, max_cnt[MAX_W];
int dfs(int idx, int val, int cnt)
{
int i, j, k;
if (idx == 2)
return 1;
visit[idx] = tm;
for (i = 1; i <= N; i++) {
if (visit[i] == tm)
continue;
j = map[idx][i];
for (k = 0; j && !(j % val); k++)
j /= val;
if (k < cnt)
continue;
if (dfs(i, val, cnt))
return 1;
}
return 0;
}
__inline int calc(int val, int r)
{
int l, m;
l = 0;
while (l <= r) {
m = (l + r) / 2;
tm++;
if (dfs(1, val, m))
l = m + 1;
else
r = m - 1;
}
return r;
}
int main()
{
int i, j, val, p, cnt;
__int64 r;
freopen("e:\\test\\in.txt", "r", stdin);
prime[prime_cnt++] = 2;
for (i = 3; i < MAX_W; i++) {
for (j = 0; j < prime_cnt && (i % prime[j]); j++);
if (j == prime_cnt)
prime[prime_cnt++] = i;
}
scanf("%d", &N);
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
scanf("%d", &map[i][j]);
for (i = 2; i <= N; i++) {
val = map[1][i];
for (j = 0; j < prime_cnt && val >= 1; j++) {
p = prime[j];
for (cnt = 0; !(val % p); cnt++)
val /= p;
if (cnt > max_cnt[j])
max_cnt[j] = cnt;
}
}
for (i = 0; i < prime_cnt; i++) {
if (!max_cnt[i])
continue;
max_cnt[i] = calc(prime[i], max_cnt[i]);
}
r = 1;
for (i = 0; i < prime_cnt; i++) {
if (!max_cnt[i])
continue;
for (cnt = 0; cnt < max_cnt[i]; cnt++)
r *= prime[i];
}
printf("%I64d\n", r);
return 0;
}