自动搬运

查看原文

来自洛谷，原作者为

	年年有年 **

搬运于2025-08-24 22:53:41，当前版本为作者最后更新于2024-07-30 17:57:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

对正常做法的一个小改进能得到更好的 1log 复杂度。

下面取 $V=10^{18}$。

考虑维护区间 $\text{lcm}$ 或者“区间 $\text{lcm}$ 已经大于 $V$”这一信息。修改的时候如果区间 $\text{lcm}$ 大于 $V$ 就暴力递归 pushup，否则如果区间 $\text{lcm}$ 不是 $x$ 的约数才暴力递归，并且 pushup 的时候不需要求左右儿子的 $\text{lcm}$，而是直接把当前结点的 $\text{lcm}$ 对 $x$ 取 $\gcd$。

分析复杂度：

容易发现，如果一个结点被暴力递归过至少一次，其 $\text{lcm}$ 一定是 $\le V$ 的。那么此后对这个结点的暴力递归就是对某个数连续取 $\gcd$ 的复杂度。以防有人不知道就说一下，辗转相除的时候递归 $O(1)$ 次能够使被连续取 $\gcd$ 的数减半。而且显然暴力递归的次数是 $O(n\log V)$，所以这部分的时间复杂度是 $O(n\log V)$。并且由于线段树链状的递归结构，非暴力递归的部分是一个连续取 $\text{lcm}$ 状物，复杂度和上面类似的，就是 $O(\log n+\log V)$。

总时间复杂度 $O(n\log V+q(\log n+\log V))$。实际上并不会更快，代码就不放了。