Iなんです
WorldMachine
·
·
题解
有这样一个好想法：回滚莫队，维护奇数和偶数长度的答案，区间变长的时候奇数从偶数处转移，偶数从奇数处转移。不幸的是我不会转移，于是我想了一种更恶心的做法。
类比 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)$，常数不小，但别写太劣就能过。
代码应该不会很短，慢慢写。