AT_abc238_g [ABC238G] Cubic? 题解

Elairin176 · 2024-08-26 14:14:07 · 题解

传送门

题意

给定一个长度为 n 的数列 a，q 次询问一段区间 [l,r] 的积是否为完全立方数。

解法

这是一个完全 \mathcal{O}(q\sqrt n) 的做法，且常数严格优于其他自称是这个复杂度的做法。
应该是目前除哈希外的最优解。
我们注意到，一个完全立方数进行质因数分解后，每个质数相对应的指数一定是 3 的倍数，反之也成立。
那么我们可以对 a 数列中的所有数进行质因数分解。
注意到 a_i\le10^6，且质因数分解后大于其根号的质数最多只有一个，故我们可以考虑根号分治。
令 m=\max\limits_{i=1}^n a_i（即值域），则对于不大于 \sqrt m 的质因数，我们可以直接使用前缀和判断。这一部分的复杂度是 \mathcal{O}(n\operatorname{p}(\sqrt m)) 的。其中 \operatorname{p}(n) 表示不大于 n 的质数数量，本题为 168。
对于大于 \sqrt m 的质因数，我们可以对所有询问离线跑莫队。莫队的过程中实时记录每个质因数的出现次数和不为 3 倍数的质因数数量即可。这一部分的复杂度是 \mathcal{O}(q\sqrt n) 的。
那么本题就结束了，总复杂度 \mathcal{O}(q\sqrt n+n\operatorname{p}(\sqrt m))，当然这里也可以看作是 \mathcal{O}(q\sqrt n)。
Code