CF1325E Ehab's REAL Number Theory Problem

给定一个长度为 $n$ 的数组 $a$，该数组有一个特殊条件：数组中的每个元素的约数个数不超过 7。请你找到一个最短的非空子序列，使得该子序列所有元素的乘积是一个完全平方数，并输出该子序列的长度。 如果 $a$ 是数组 $b$ 的一个子序列，则 $a$ 可以通过从 $b$ 中删除若干（可能为零或全部）元素得到。

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$），表示数组 $a$ 的元素。

输出一个整数，表示满足条件的最短非空子序列的长度。如果存在多个最短子序列，可以输出任意一个。如果不存在这样的子序列，输出 “-1”。

在第一个样例中，你可以选择子序列 $[1]$。 在第二个样例中，你可以选择子序列 $[6, 6]$。 在第三个样例中，你可以选择子序列 $[6, 15, 10]$。 在第四个样例中，不存在满足条件的子序列。 由 ChatGPT 4.1 翻译