prow2012-A3-0001

从 Trac 迁移的文章

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

原文章内容如下：

题意是在问有向图上的1->n路径，
路径上到某个点的得分是其所有前缀节点点权的LCM，
求出终点得分为k的路径数量。

要求每次的行走必须使得答案不一样。

考虑到一个合法路径，途中的每个分值必须是K的约数（否则最后LCM不可能为K）

以f[i][j](i为当前走到的点，j为当前路径得到的分值）DP，

j的取值可能到10^6

而有效j（K的约数）数量<2000，于是考虑用有效j进行DP。

f[i][j]前推到-->f[next_node][Num[j]*val[next_node]/gcd()]

题意是在问有向图上的1->n路径，

路径上到某个点的得分是其所有前缀节点点权的LCM，

求出终点得分为k的路径数量。

要求每次的行走必须使得答案不一样。

考虑到一个合法路径，途中的每个分值必须是K的约数（否则最后LCM不可能为K）

以f[i][j](i为当前走到的点，j为当前路径得到的分值）DP，

j的取值可能到10^6

而有效j（K的约数）数量<2000，于是考虑用有效j进行DP。

f[i][j]前推到-->f[next_node][Num[j]*val[next_node]/gcd()]