51nod 1610

题目

神犇题解

所以说鄙人的姿势水平完全不够啊OTZ。

很naive的想法是O（T*v*m）的，据说卡一卡可以过去。题目要求的东西其实是这个： $ sumlimits_{i = 1}^v {mu (i) * su{m_i}}  $ 其中v是值域范围，sum是以这个值为gcd的路径总数。那么怎么修改呢？修改其实等价于删除再增加，我们用floyd来更新就好啦。

复杂度：O（m*n*n+T*n*n）