设a与1 和2 均相连，则按楼主所说， 1和2 之间的最小公倍数 ， 等于1 和 a 之间的最小公倍数和2 和a之间的最小公倍数的最大公约数 和1和2 之间原有的最小公倍数的最小公倍数，为什么呢？ 其实很简单， 因为1 和a 的所有路径的每个质因子都会被2 和a 的所有路径的每个质因子筛一遍， 把所有相同的留下（即最大公约数）， 再求最小公倍数， 因此就可作出楼主的Floyd优化， 真是太妙了。


其实这道题根本没有这么难， 用最简单的深搜加剪枝就可轻易做到0ms 
剪枝： 如果所走路径的最大公约数能被现有解整除， 就return ；

但仔细想想， 如果题目给出很多组查询， 楼主的方法则更为适用。