zrj2012-A3-0001

从 Trac 迁移的文章

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

原文章内容如下：

题目大意是说，有一个有向图，每个顶点有一个值pi。你有一个属性a，一开始你在点1，且a=p1。
如果你走到点i，a会变成lcm(a,pi)，不过如果原本的a与lcm(a,pi)相同，即你走到点i后，a的值没有变化，这个走法就不可行。
最后求走到点n，且a=k的方案数。
很明显，由于a是以不断与其他数求最小公倍数变化的，并且最后要变成k，那么a一定是单增的，并且a必须始终是k的约数。
k《10^6，那么k的约数只有sqrt(k)的级别。因此我们可以用f[i][j]表示走到点i，a等于k的第j个约数时的状态数。
虽然图可以有环，但是由于a是递增的，我们可以以a为外层状态，然后枚举每个点，再沿着从这个点连出去的路拓展。

题目大意是说，有一个有向图，每个顶点有一个值pi。你有一个属性a，一开始你在点1，且a=p1。

如果你走到点i，a会变成lcm(a,pi)，不过如果原本的a与lcm(a,pi)相同，即你走到点i后，a的值没有变化，这个走法就不可行。

最后求走到点n，且a=k的方案数。

很明显，由于a是以不断与其他数求最小公倍数变化的，并且最后要变成k，那么a一定是单增的，并且a必须始终是k的约数。

k《10^6，那么k的约数只有sqrt(k)的级别。因此我们可以用f[i][j]表示走到点i，a等于k的第j个约数时的状态数。

虽然图可以有环，但是由于a是递增的，我们可以以a为外层状态，然后枚举每个点，再沿着从这个点连出去的路拓展。