一、问题分析 题目要求统计序列中所有乘积为完全平方数的区间 $(l, r)$（$1 \leq l \leq r \leq n$），并按字典序输出这些区间（若超过 $10^5$ 个，仅输出前 $10^5$ 个）。

完全平方数的核心性质：其质因数分解后，所有质因子的指数均为偶数。

由此可推导出区间乘积为完全平方数的充要条件：区间内所有数的质因子指数之和为偶数。

二、关键思路

1. 质因子奇偶性表示（特征向量） 对每个数 $a_i$，分解为质因子后，仅保留各质因子指数的奇偶性（偶数记为 $0$，奇数记为 $1$），形成该数的「特征向量」。

示例：

$4 = 2^2$ → 质因子 $2$ 的指数为偶数 → 特征向量中 $2$ 对应的位置为 $0$

$6 = 2^1 \times 3^1$ → 质因子 $2$、$3$ 的指数均为奇数 → 特征向量中 $2$、$3$ 对应的位置均为 $1$

2. 前缀异或转化 定义「前缀异或数组」$pre$，其中 $pre[i]$ 表示前 $i$ 个数的特征向量的异或和（异或运算：$0⊕0=0$，$0⊕1=1$，$1⊕1=0$）。

区间 $[l, r]$ 的乘积是否为完全平方数，等价于：pre[r]=pre[l−1]

原因：$pre[r] \oplus pre[l-1]$ 对应区间 $[l, r]$ 的特征向量异或和，若结果为 $0$，说明所有质因子指数和为偶数。

3. 哈希计数 用哈希表统计每个特征向量（即 $pre[i]$）的出现次数：

若某特征向量出现 $c$ 次，从这 $c$ 个位置中任选 $2$ 个（记为 $i$ 和 $j$，$i < j$），均可构成满足条件的区间 $(i+1, j)$

对应的区间数量为组合数 $C(c, 2) = \frac{c \times (c-1)}{2}$

三、实现步骤

1. 特征向量的压缩表示 直接存储特征向量（可能包含大量质因子）不现实，需通过「哈希值」压缩：

为每个首次出现的质因子分配唯一编号（如按出现顺序递增，如第一个质因子编号为 $0$，第二个为 $1$，以此类推）

特征向量的哈希值 = 所有 "指数为奇数的质因子编号" 的异或结果（异或运算天然适合奇偶性组合，且计算高效）

2. 大数质因数分解（应对 $a_i \leq 10^{36}$） 由于 $a_i$ 最大可达 $10^{36}$，需结合两种分解方法：

试除法：优先处理小质因子（如 $\leq 10^6$），快速分解常见小质数

Pollard-Rho 算法：处理大质因子（适用于 $10^{18}$ 以上的数），是高效的大数分解算法

3. 统计与输出 统计总区间数：遍历哈希表，对每个特征向量的出现次数 $c$，累加 $C(c, 2)$ 得到总区间数

生成区间：为每个特征向量记录对应的前缀索引列表（如 $pre[i_1] = pre[i_2] = \dots = pre[i_c]$，则索引列表为 $[i_1, i_2, \dots, i_c]$），遍历列表生成所有 $(i_k + 1, i_m)$（$k < m$），按字典序输出（因索引列表天然递增，生成的区间已满足字典序）

四、算法复杂度 质因数分解：Pollard-Rho 算法期望时间复杂度 $O(n^{1/4})$ 每数

特征向量计算：$O(n \cdot k)$，其中 $k$ 为平均质因子数

统计与输出：$O(n + m)$，其中 $m$ 为输出区间数（不超过 $10^5$）