网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
考验
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | testz.in | 输出文件 | testz.out |
【题目描述】
话说高考研讨会上有许多志愿者,其中有许多女生,性格开朗、活泼的 zn 很快就与这 些女生打成一片,把 z 同学晾在了一边。现场人很多,小 z 一转眼发现找不到了 zn 一伙人 了,肿么办,计划赶不上变化啊,小 z 找到了志愿者总管:一个带着小红帽的家伙,小红帽说了:想知道她在哪啊,听说你是 410 的,听说 410 都是些牛逼人啊,我得考考你。
小红帽出题了,咱们现在处于 1 区域,zn 处于 2 区域,一共有n个区域,有一些路连接着两个区域,路有长度,小红帽规定一条从 1 到 2 的路径的权值为这条路上每条路长度的最大公约数,他叫你求出所有能从 区域 1 到 2 的路径的权值的最小公倍数(路径上的点最多经过一次) 。
【输入格式】
第一行:n
接下来是一个 n*n 的矩阵,i行j列的值代表从 i区域到 j区域的路径长度,若不连通,则为 0
【输出格式】
所求的最小公倍数
【样例输入】
4
0 0 3 16
0 0 9 6
3 9 0 0
16 6 0 0
【样例输出】
6
【提示】
2≤n≤25
1<路径的权值<2000
Hint:不用高精度哦
【来源】
在此键入。