思路当一个数是完全平方数的时候，它的所有质因子的次数都是偶数。记\(x\)的质因子为\(p_1^{q1}\timesp_2^{q2}\timesp_3^{q3}...\timesp_v^{qv}\)。这些数可以通过次数的奇偶性用一个\(v\)位的二进制串\(B\)表示，\(B_i\)为\(0\)说明\(q_i\)为偶数，\(B_i\)为\(

思路看到\(a_i\)很小，不难想到状压一类的东西。考虑把每个数的质因数当做二进制位，这个二进制位的\(1/0\)代表含有这个质因数的奇偶，再做一个异或前缀和，显然完全平方数的质因子个数一定为偶数，根据异或的性质，两个相同的数异或才为\(0\)所以只需要找到异或前缀和中相同的数的个