思路：
首先每條路徑的值都可以分解一下質(zhì)因數(shù)，就可以表示為多個質(zhì)數(shù)的冪相乘的形式，
比如 2^6 * 3^8 * 17^22 * 23^1。
三個數(shù)字a, b, c求最大公約數(shù)，分解完質(zhì)因數(shù)后：
如果a擁有2^8，b擁有2^10，c擁有2^4。那最大公約數(shù)必然擁有2^4，取最小的一個。
對于每個質(zhì)數(shù) 2, 3, 5, 7。。都是這個道理。
如果是求最小公倍數(shù)，在剛剛的例子里，就是取最大的一個了。
在點之間行走的過程，可以這樣來看。在點1的時候GCF的值是所有質(zhì)數(shù)的最大次冪的乘積。
GCF的值必定是越走越小。
每經(jīng)過一條路徑，CGF各個質(zhì)因數(shù)的冪都必須小于等于路徑的對應(yīng)的值。
就好比路徑就只能容納這么大的流量。然后到達點2的時候，看看哪條路徑的流量最大。
看起來像最大流問題，但不是最大流問題。
我們沒辦法遍歷一次圖，就求出哪條路徑的流量最大。
但由于路徑的權(quán)值最大才2000，質(zhì)因數(shù)的冪最大也只有11（2^11 = 2048），大不了每個冪都試一次。
用二分法就可以了。
對于每一個質(zhì)數(shù)，求到達點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;
}