前30分的随机异或权是简单的。

看到如此巨大的数据范围发现显然不能做乘法，再联系异或相消的性质容易想到gcd，这样可以得到一个 $n^3 \log n$ 的做法：把每个数拿出来和区间内的其他数做gcd，然后从两数中把gcd除掉，最后检查下整个区间内剩下的数是否都是完全平方数即可。

发现样例中并没有给这个复杂度的样例，于是抱着试试看的心态跑了下 $1000$ 的样例，惊喜地发现只跑了十秒左右，打开样例答案发现区间数只有六十个左右，感觉进行一些精妙的卡常或许可以水过去。

观察样例2中几个数字的生成方式，猜测是用若干素数相乘，再猜测出题人或许比较懒，不会找很多大素数，于是可以直接用前 $1000$ 个素数做随机异或权（直接把第一个包的代码粘过来），在该情况下不成立的区间在所有情况下均不成立，不去check这些区间，这样再跑 $1000$ 的大样例发现只跑了一秒不到，非常震撼。

这样就可以在完全不会二次剩余的情况下在一个小时以内拿到 $70$ 分的较高分数，且代码非常好写。