题目描述:
You are given an integer array \(a_1,a_2,…,a_n (1≤a_i≤n).\)
Find the number of subarrays of a whose XOR has an even number of divisors. In other words, find all pairs of indices \((i,j) (i≤j)\) such that \(a_i⊕a_{i+1}⊕⋯⊕a_j\) has an even number of divisors.
For example, numbers \(2, 3, 5\) or \(6\) have an even number of divisors, while \(1\) and \(4\) — odd. Consider that 0 has an odd number of divisors in this task.
Here XOR (or \(⊕\)) denotes the bitwise XOR operation.
Print the number of subarrays but multiplied by 2022... Okay, let's stop. Just print the actual answer.
输入描述:
Each test contains multiple test cases. The first line contains the number of test cases \(t (1≤t≤10^4)\). Description of the test cases follows.
The first line of each test case contains a single integer \(n (2≤n≤2⋅10^5)\) — the length of the array \(a\).
The second line contains n integers \(a_1,a_2,…,a_n (1≤a_i≤n)\).
It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2⋅10^5\).
输入描述:
For each test case, print the number of subarrays, whose XOR has an even number of divisors.
样例:
input:
4
3
3 1 2
5
4 2 1 5 3
4
4 4 4 4
7
5 7 3 7 1 7 3
output:
4
11
0
20
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int T = 1;
LL n;
void solve()
{
scanf("%lld", &n);
vector<int> a(n), b(2 * n); // 开两个vector,一个用于存数组,一个用于存某个数出现的次数
a.clear(), b.clear();
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
LL cnt = 0; // 存储异或和的因数为奇数个的数的个数
int t = 0;
b[t]++; // a[0] ^ a[0]为0
for (int i = 0; i < n; i++)
{
t ^= a[i];
// cout << t << ' ';
// n个数可能的异或最大值肯定小于2 * n
// 判断某个数的因数是否为奇数的条件就是判断其是否是完全平方数
for (LL j = 0; j * j < 2 * n; j++)
{
// 一个数 t 异或一个完全平方数的结果,该结果异或 t的结果必定是那个完全平方数
if ((t ^ (j * j)) < 2 * n)
{
cnt += b[t ^ (j * j)]; // cnt 加上这个数出现过的次数
cout << t << ' ' << j * j << ' ' << (t ^ (j * j)) << ' ' << cnt << '\n';
}
}
b[t]++; // t的出现的次数加一
}
LL ans = (n * (n + 1) / 2) - cnt; // 总共的个数减去不成立的个数即为成立的个数
printf("%lld\n", ans);
}
int main()
{
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
scanf("%d", &T);
while (T--)
{
solve();
}
return 0;
}
标签:Even,even,XOR,数论,Subarrays,number,int,test,divisors
From: https://www.cnblogs.com/KSzsh/p/17017080.html