\(\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\)，則有

，準確率 = \(\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\)。
於是讓我們來計算一下時間複雜度：

1. 質因數分解 \(\mathcal O(na^{0.5})\)
2. 預處理字首和 \(\mathcal O(h \log a)\)（考慮到一個數的質因數分解最多為 \(2 \times \cdots \times 2\)）
3. 詢問 \(\mathcal O(qh)\)

總時間複雜度 \(\mathcal O(na^{0.5} + h(\log a + q))\)。
考慮到時限為 \(\rm 3s\)，可以取 \(h = 300\)。
可以通過。（其實這 \(h\) 個雜湊函數也可以狀壓，大概會有 \(\dfrac 1\omega\) 的常因子優化）