给出一个正整数数组A,牛牛想知道其中有多少子数组满足 : 里面所有数字的乘积等于里面所有数字的异或。 一个数组的子数组指数组中非空的一段连续数字。给出C++代码
时间: 2023-05-29 22:06:31 浏览: 73
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100005;
int A[MAXN], cnt[MAXN], N;
vector<int> prime;
void init() { // 筛质数
bool isPrime[MAXN];
fill(isPrime, isPrime + MAXN, true);
for (int i = 2; i < MAXN; i++) {
if (isPrime[i]) {
prime.push_back(i);
for (int j = i * 2; j < MAXN; j += i) {
isPrime[j] = false;
}
}
}
}
int main() {
init();
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
int ans = 0, mul = 1, xorSum = 0, l = 0;
for (int r = 0; r < N; r++) {
cnt[A[r]]++;
while (cnt[A[r]] > 1) { // 有重复元素
cnt[A[l]]--;
mul /= A[l];
xorSum ^= A[l];
l++;
}
mul *= A[r];
xorSum ^= A[r];
if (mul == xorSum) { // 满足条件
ans++;
}
for (int i = 0; i < prime.size() && prime[i] * prime[i] <= A[r]; i++) {
int p = prime[i], cntP = 0;
while (A[r] % p == 0) {
A[r] /= p;
cntP++;
}
if (cntP > 0) {
ans += cnt[P - cntP];
}
}
if (A[r] > 1) { // 处理质因子
ans += cnt[A[r] - 1];
}
}
cout << ans << endl;
return 0;
}