自动搬运

查看原文

来自洛谷，原作者为

	WorldMachine 请引领我至夜晚熠熠闪烁的群星之下

搬运于2025-08-24 23:16:11，当前版本为作者最后更新于2025-01-23 12:59:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

有这样一个好想法：回滚莫队，维护奇数和偶数长度的答案，区间变长的时候奇数从偶数处转移，偶数从奇数处转移。不幸的是我不会转移，于是我想了一种更恶心的做法。

---

$\text{lcm}$ 就是对每个素因子的次数取 $\max$，$\gcd$ 就是对每个素因子的次数取 $\min$。

类比 min-max 反演，有：

$$\text{lcm}(T)=\prod_{S\subseteq T,S\not=\varnothing}(\gcd(S))^{(-1)^{|S|-1}} $$

要求所有长度为奇数的子序列的 $\gcd$ 的平方之积，即：

$$\text{lcm}([l,r])\cdot\prod_{S\subseteq [l,r],S\not=\varnothing}\gcd(S) $$

于是问题变成两部分：求区间 $\text{lcm}$，以及求区间内所有子序列的 $\gcd$ 之积。

---

第二部分，考虑根号分治。

对于 $p\le\sqrt V$，设区间 $[l,r]$ 内 $p$ 次数为 $k$ 的数个数为 $\text{cnt}_k$，那么 $p$ 的贡献（次数）为：

$$\sum_{i=1}^{\lfloor\log_pV\rfloor}i\left(2^{\text{cnt}_i}-1\right)2^{\sum\limits_{j=i+1}^{\lfloor\log_pV\rfloor}\text{cnt}_j} $$

预处理 $2$ 的次幂，注意到次数会很大所以记得对 $998244352$ 取模。对于每个 $p$ 可以花 $\mathcal O(\log V)$ 的时间获得这部分的答案，这部分时间复杂度为 $\mathcal O\left((n+q)\cdot\dfrac{\sqrt V}{\log V}\cdot\log V\right)=\mathcal O((n+q)\sqrt V)$。

对于 $p>\sqrt V$，性质是每一个 $a_i$ 至多会有一个这样的 $p$。莫队，设当前 $p$ 的出现次数为 $\text{cnt}_p$，那么 $p$ 的贡献为 $p^{2^{\text{cnt}_p}-1}$，那么当前的答案为：

$$\prod_{p>\sqrt V}p^{2^{\text{cnt}_p}-1}=\dfrac{\prod\limits_{p>\sqrt V}p^{2^{\text{cnt}_p}}}{\prod\limits_{p>\sqrt V}p} $$

考虑如何计算分子。

正常的做法是，维护 $\text{pow}_p=p^{2^{\text{cnt}_p}}$，区间扩大时直接将 $\text{pow}_p$ 平方顺便更新答案（所以还要维护一个 $\text{pow}^{-1}_p$），缩小时就寄了，所以要使用回滚莫队。

其实不用回滚莫队，设 $\text{pow}_{p,k}=p^{2^k}$，这个可以把 $2^k\bmod 998244352$ 预处理出来，再预处理每个素数的光速幂，当然 $\text{pow}_{p,k}^{-1}$ 也一样地搞，这样就可以使用普通莫队了，但不好说哪个更快。

upd：我好像学了个假的数据结构……上面的东西直接用指针数组搞出每个数要用到的值即可，总数是 $n$ 的。

第二部分时间复杂度为 $\mathcal O((n+q)\sqrt V+n\sqrt q)$。

---

尝试解决第一部分。有了第二部分的基础其实是简单的。

对于 $p\le\sqrt V$ 就是一个区间最大值，可以简单地做到 $\mathcal O((n+q)\sqrt V)$。

如果 $p>\sqrt V$，每个 $p$ 的次数至多为 $1$，大力做莫队即可。

第一部分时间复杂度为 $\mathcal O((n+q)\sqrt V+n\sqrt q)$。

---

结算：$n,m,V$ 均同级，时间复杂度为 $\mathcal O(n\sqrt n)$，常数不小，但别写太劣就能过。

代码应该不会很短，慢慢写。