题意：对于一个序列 ，定义其权值为满足 为平方数的 的个数。
现在 中含有数 ，求可能的最大权值。
，时限 。
两个数相乘为完全平方数的充要条件：奇次数质因子集合相同。
按奇次数质因子集合给数分类，将同类的数放在一起，则权值为 。显然这是上界了，现在的目标就是求等价类个数。
将数 写成二元组 ，其中
是奇次数质因子的积（每个质因子只乘一次，即不含平方因子）， 是 （显然剩余部分 是完全平方数），这是个双射。
等价类个数即为
的种类数，枚举每个 ，考虑是否存在一个 与其对应。
显然 以内 的数目为 ，答案可列式
对
整除分块，会分成
块。对于每一块，需要求出
的部分和。
众所周知 。这能 整除分块计算。
计算分块套分块的复杂度。枚举 ，则有 。
当 时，复杂度为
。
当 时，则有 ，复杂度为 。
此外线性筛 已经需要 的复杂度。