自动搬运

查看原文

来自洛谷，原作者为

	水星湖 菜

搬运于2025-08-24 23:12:02，当前版本为作者最后更新于2025-03-29 19:33:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑到每个 $a_i$ 大于 $10^4$ 的质因子至多只有一个，可以树上莫队维护路径不同数个数 （SP10707），时间复杂度 $\mathcal O(n\sqrt q)$。枚举小于 $10^4$ 的质数，对于每个质数就是要查 $q$ 条路径上是否出现过这个质数，可以前缀和做到 $\mathcal O(n+q)$，总复杂度 $\mathcal O(n\sqrt q + \pi(\sqrt V) (n+q))$。

然后发现：

因为我没写代码，写了发现真卡不过（5.6s）。

怎么办呢？

这样复杂度就是 $\mathcal O(n\sqrt q + \pi(\sqrt[3]V) (n+q))$，而且还可以保证莫队修改常数比较小。

最优解第二。

让我们膜拜 Cai 老师/bx