\(\text{ABC 238 G}\)
题意
给定一个序列 \(a\)，和 \(q\) 次询问，每次询问询问是否有
\[\exists k \in \mathbb N, \prod_{i=l}^r a_i = k^3 \]
非正解
显然可以对 \(a_i\) 进行质因数分解，并预处理出每个质因数的前缀和，则可以在 \(\mathcal O(n^{1.5} + q \times \dfrac {a}{\ln a})\) 的时间内暴力解决。
注意到做的前缀和相当于三进制不进位加法，则定义 \(A_i\) 为 \(A\) 中三进制位为 \(i\) 的位编号的集合，
则会有
，\(\tt bitset\) 优化即可，时间复杂度：\(\mathcal O(n^{1.5} + q \times \dfrac {a}{\omega \ln a})\)，其中 \(\omega \approx 10\)。
题解
考虑用哈希函数解决本题。如果存在一个函数 \(f(x) : \mathbb N^{\mathcal O(a/\ln a)} \to \mathbb N\)（输入实际上是质因数分解），满足 \(f(a + b) = f(a) + f(b)\)，且存在一个性质 \(P(x)\)，使得 \(P(f(x))\) 是 \(x\) 对应的整数是立方数的必要条件，就称 \(f\) 是一个哈希函数。
于是，对于任意的 \(\{x_i\}\)，有
是哈希函数。
证明：
\(P(k) \iff 3 \mid k\)：如果 \(a\) 对应的整数是立方数，则有 \(\forall i, 3 \mid a_i\)，此时，\(f(a)\) 的每一项都 \(\equiv 0 \pmod 3\)，故成立。
线性性成立：
。
我们来分析哈希函数的正确率：
对于一个如上构造的哈希函数 \(f\)，设一个区间是立方数的概率为 \(p\)，则有
| 概率表 | 是立方数 | 非立方数 |
|---|---|---|
| 预测正确 | \(p\) | \(\dfrac 23\) |
| 预测错误 | \(0\) | \(\dfrac 13-p\) |
，准确率 = \(\dfrac{{准确预测}}{{总预测}} = p + \dfrac 23 \ge \dfrac 23\)，失误率 \(\le \dfrac 13\)，就定义最高失误率 \(l := \dfrac 13\)。
设我们有 \(h\) 个哈希函数，则 \(h\) 个哈希函数都失误的概率为 \(l^h\)，定义 \(L := l^h\)。因为我们有 \(Q\) 次询问，则至少有一个哈希函数失误的概率为 \(1 - (1 - L)^Q\)，我们将证明这个柿子 \(\le QL\)：
数学归纳法：
- \(Q = 1\) 时左 \(= 1 - (1 - L) = L\)，右 \(= 1L = L\)（总不可能零次询问吧）
- \(Q \gt 1\) 时：
进行移项，化为 \((1 - L)^Q \ge 1 - QL\)，进行变换：
\(\begin{array}{l} (1 - L)^Q \ge 1 - QL \\ (1 - L)^{Q - 1} (1 - L) \ge 1 - QL \\ (1 - L)^{Q - 1} \ge 1 - (Q - 1)L \\ (1 - (Q - 1)L) (1 - L) \ge 1 - QL \\ 1 - (Q - 1)L - L(1 - (Q - 1)L) = 1 - QL + (Q - 1)L \ge 1 - QL \end{array}\)
证毕。
设有 \(c\) 个测试点，则失误率 \(\le c \times q \times l^h\)。
于是让我们来计算一下时间复杂度：
- 质因数分解 \(\mathcal O(na^{0.5})\)
- 预处理前缀和 \(\mathcal O(h \log a)\)（考虑到一个数的质因数分解最多为 \(2 \times \cdots \times 2\)）
- 询问 \(\mathcal O(qh)\)
总时间复杂度 \(\mathcal O(na^{0.5} + h(\log a + q))\)。
考虑到时限为 \(\rm 3s\)，可以取 \(h = 300\)。
可以通过。（其实这 \(h\) 个哈希函数也可以状压，大概会有 \(\dfrac 1\omega\) 的常因子优化）