CF1028H Make Square

我们称一个数组 $b_1, b_2, \ldots, b_m$ 是好的，如果存在两个下标 $i < j$，使得 $b_i \cdot b_j$ 是一个[完全平方数](https://en.wikipedia.org/wiki/Square_number)。 给定一个数组 $b_1, b_2, \ldots, b_m$，你每次操作可以执行以下两种之一： - 将任意一个元素 $b_i$ 乘以任意一个质数 $p$； - 如果 $b_i$ 能被质数 $p$ 整除，则将 $b_i$ 除以 $p$。 记 $f(b_1, b_2, \ldots, b_m)$ 为将数组 $b$ 变为好的所需的最少操作次数。 现在给定一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$，以及 $q$ 个询问，每个询问为 $l_i, r_i$。对于每个询问，输出 $f(a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i})$。

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 194\,598$，$1 \le q \le 1\,049\,658$）——数组长度和询问数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 5\,032\,107$）——数组的元素。 接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i < r_i \le n$）——每个询问的参数。

输出 $q$ 行，每行一个答案，表示每个询问的结果，顺序与输入一致。

在第一个样例的第一个询问中，你可以将第二个数乘以 $7$ 得到 $259$，再将第三个数乘以 $37$ 得到 $1036$。此时 $a_2 \cdot a_3 = 268\,324 = 518^2$。 在第二个询问中，子数组已经是好的，因为 $a_4 \cdot a_6 = 24^2$。 在第三个询问中，你可以将 $50$ 除以 $2$ 得到 $25$。此时 $a_6 \cdot a_8 = 30^2$。 由 ChatGPT 4.1 翻译