第四题其实有个O(N)的解法 不过最后没写完，写了个效率比较高的O(N^2)交了，还是平时不刷题的锅，调试花的时间太长了 对于每个数A[i]，有意义的只是A[i]在分解质因数之后有哪些质因子有奇数个。因为100以内只有26个质数，可以用一个int的26位字节记录一个数分解之后的状态T[i]。对两个数A[i]和A[j]，B[i]异或B[j]即为相乘后的结果<br />对于一段序列A[i]~A[j]，如果B[i]~B[j]全部异或后结果为0，A[i]~A[j]乘积即为完全平方数<br />在这个方案下暴力O(N^2)枚举一遍所以可能的序列，就是我80的做法<br />但是其实可以额外维护一个序列P和一个hash set Q，P[i]表示前B[0]~B[i]异或的结果，Q[i]=x表示B[0]~B[x]异或为i，如果有不止一个x满足条件，取最小的x<br />基于这样的两组数据，在对A[i]进行处理时，P[i]=P[i-1]^B[i]，A[Q[P[i]]+1]~A[i]就是以A[i]为结尾的最长完全平方子序列