Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我来给不明白的同学解释一下 && 提出一种 针对本题数据的更快的算法

Posted by 117474335 at 2010-09-30 09:20:34 on Problem 2132 and last updated at 2010-09-30 09:33:10
In Reply To:Floyd,用这个 Posted by:applepi at 2010-09-29 15:32:28
设a与1 和2 均相连,则按楼主所说, 1和2 之间的最小公倍数 , 等于1 和 a 之间的最小公倍数和2 和a之间的最小公倍数的最大公约数 和1和2 之间原有的最小公倍数的最小公倍数,为什么呢? 其实很简单, 因为1 和a 的所有路径的每个质因子都会被2 和a 的所有路径的每个质因子筛一遍, 把所有相同的留下(即最大公约数), 再求最小公倍数, 因此就可作出楼主的Floyd优化, 真是太妙了。


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

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

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator