题目描述
给定一个包含 n 个正整数的序列 A = [a₁, a₂, …, aₙ]。需从中找出一个子序列，使得该子序列中任意两个不同元素的乘积都是一个完全平方数。求满足条件的最长子序列的长度。
说明
-
子序列：从原序列中删除零个或多个元素，其余元素保持原有顺序得到的序列（例如，[2, 3, 18] 是 [2, 8, 3, 18, 12] 的一个子序列）。 -
完全平方数：一个整数可以表示为另一个整数的平方（例如，36 = 6²，是完全平方数）。
输入格式
-
第一行包含一个整数 n，表示序列的长度。 -
第二行包含 n 个用空格隔开的正整数 a₁、a₂、…、aₙ，表示序列中的元素。
输出格式
输出一个整数，表示满足条件的最长子序列的长度。
输入输出样例
|
|
|
|---|---|
|
2 8 3 18 12 |
|
样例解释
满足条件的子序列为 [2, 8, 18]，其任意两个元素的乘积（2×8=16、2×18=36、8×18=144）均为完全平方数，长度为 3。
数据范围
对于 100% 的数据，满足 1 ≤ n ≤ 10⁵，1 ≤ aᵢ ≤ 10⁷。
