team2012-B2-sol-0001

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意：有n个点(n <= 2000)的无向图，其分数为路径上所有点点权的最小公倍数，现在需要从1走到n，并且在移动过程中分数必须发生改变，求到达终点时分数为k(k < 1000000)的方案数
思路：因为是最小公倍数，移动过程中的分数必定是k的约数，从k的范围看k的约数不会超过2000个（一般非常少），可以用F[i][j]记录移动到点i，并且分数为j的方案数。因为移动过程中分数一定要变，说明转移只能是从分数小的到大的，这是有方向的，使用DP可以快速解决这一问题。

题意：有n个点(n <= 2000)的无向图，其分数为路径上所有点点权的最小公倍数，现在需要从1走到n，并且在移动过程中分数必须发生改变，求到达终点时分数为k(k < 1000000)的方案数

思路：因为是最小公倍数，移动过程中的分数必定是k的约数，从k的范围看k的约数不会超过2000个（一般非常少），可以用F[i][j]记录移动到点i，并且分数为j的方案数。因为移动过程中分数一定要变，说明转移只能是从分数小的到大的，这是有方向的，使用DP可以快速解决这一问题。