题目链接：https://codeforces.com/contest/1731/problem/C
题目的大致意思是：给长度为n的数组，求 子数组的异或和 的 结果 的 除数个数 为 偶数个 的 子数组 有多少个。
例如：4的除数有1，2，4，有三个，所以4的除数为奇数个；8的除数有1，2，4，8，有四个，所以8的除数有偶数个；
通过题意，我们可以发现，这题的切入点在于 异或和 与 除数个数为偶数 ；
首先，我们先想一个数x，他的除数的个数为偶数的时，x会有什么特点。
我们可以想到，如果y是x的除数，那么x/y也是x的除数，当y与x/y不相等的时候，x的除数会增加2个；
当y与x/y相等的时候，x的除数会增加1个；
而y与x/y相等的条件在于，x是y的平方；
于是，我们可以知道，当一个数是平方数的时候，他的除数个数为奇数个；
观察n的范围是2e5，可以发现平方数大致在1e3左右（不到），可以先预处理出平方数；
那么除数的个数为偶数我们已经解决了，接下来就是解决异或和的事情；
在我们知道哪些数满足除数的个数是偶数的时候，我们会先暴力的想到，枚举每个区间，去计算他们的异或和，是否是平方数。
显然，暴力是不行，时间复杂度不能让我们这样子去做。
于是，我们可以思考异或前缀和，异或具有一个比较好的性质在于，x^y = z--->y^z = x,x^z = y;
假设当前我们异或到第i个数的结果是x，然后假设y是一个平方数，那么x^y得到的结果z，如果z在后面前缀异或和中出现了(假设是第j个）；
根据前缀异或和的性质，z^x就是[ i , j ]这段区间异或和的结果，然后因为x^y = z,可以得到z^x = y，而y是平方数；
那么我们就可以枚举平方数去和x进行异或，看后面z出现的个数，然后减去即可；
时间复杂度O（700N）；
代码如下：
#include<bits/stdc++.h>
int odd[550000], op = 0;
signed main()
{
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
for (int i = 0; i * i <= 5e5; ++i)//预处理出5e5以内的平方数，
odd[op++] = i * i; //为什么不是2e5，是因为异或后出现的结果可能会比原来大
//所以需要多预处理一些
std::vector<int> MP(262144 * 2, 0);//记录前缀异或和出现的个数
int T; std::cin >> T;
while (T--)
{
int n; std::cin >> n;
int pre = 0;
std::vector<int> nums(n + 1, 0);
for (int i = 1; i <= n; ++i)
std::cin >> nums[i], pre ^= nums[i], MP[pre]++;
long long ans = 0; pre = 0;
for (int i = 1; i <= n; ++i)
{
int cnt = 0; pre ^= nums[i]; MP[pre]--; pre ^= nums[i];//这里稍微有点绕
for (int k = 0; k < op; ++k) //需要先把当前的前缀异或和给减去，因为0^pre的话，会重复计数
{
cnt += MP[pre ^ odd[k]];
if (odd[k] == nums[i])cnt++;
}
ans += (n - i - cnt + 1); pre ^= nums[i];//把满足的结果累加
}
std::cout << ans << "\n";
}
return 0;
}
这题需要想到平方数和异或前缀和，需要分开来想。（一开始是想 异或和 与 除数个数为偶数的关系是什么，结果想了好久，悲~还得训训）
标签：Even,std,平方,Divide,841,int,个数,异或,除数 From： https://www.cnblogs.com/ACMER-XiCen/p/17011177.html