A32196. 区间乘积题面描述小杨有一个包含 n 个正整数的序列 A=[a1，a2 ......，an ]。小杨想知道有多少对 <l，r> (1<=l<=r<=n) 满足al * al+1 * ........ar 为完全平方数。一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得 x = y*y。
填空题
困难
知识点
题目描述
区间乘积
题面描述
小杨有一个包含 n 个正整数的序列 A=[a1，a2 ......，an ]。
小杨想知道有多少对 <l，r> (1<=l<=r<=n) 满足al * al+1 * ........ar 为完全平方数。
一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得 x = y*y。
输入格式
第一行包含一个正整数 n，代表正整数个数。
第二行包含 n 个正整数 a1，a2 ......，an，代表序列 A。
输出格式
输出一个整数，代表满足要求的<l，r>数量。
样例1
输入
5
3 2 4 3 2
输出
2
满足条件的<l，r>有<3，3>和<1，5>。
数据范围
对于全部数据，保证有 1 <= n <= 100000，1 <= ai <= 30
参考答案
#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
const int N = 1e5+10;
int calc(int x) {
int res = 0;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
while (x% i == 0) {
x/= i;
res^=(1<<(i-1));
}
}
}
if (x != 1) {
res^=(1<<(x-1));
}
return res;
}
int a[N];
int main() {
int n;
cin>>n;
long long ans = 0;
int pre = 0;
for(int i=1; i<=n; i++) {
cin>>a[i];
int res = calc(a[i]);
pre^=res;
if(pre==0)
ans++;
ans+=mp[pre];
mp[pre]+=1;
}
cout<<ans<<"\n";
}
上一题
下一题