区间乘积

题目描述

⼩杨有⼀个包含 个正整数的序列 。 ⼩杨想知道有多少对 ( ) 满⾜ 为完全平⽅数。 ⼀个正整数 为完全平⽅数当且仅当存在⼀个正整数 使得 。

输入格式

第⼀⾏包含⼀个正整数 ，代表正整数个数。 第⼆⾏包含 个正整数 ，代表序列 。

输出格式

输出⼀个整数，代表满⾜要求的 数量。 3.2.4 样例1 1 5 2 3 2 4 3 2 1 2 3.2.5 样例解释 满⾜条件的 有 和 。 3.2.6 数据范围 子任务编号 数据点占比 1 20% 2 40% 3 40% 对于全部数据，保证有 ， 。 3.2.7 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 map<int,int> mp; 4 const int N = 1e5+10; 5 int calc(int x) { 6 int res = 0; 7 for (int i = 2; i * i <= x; i++) { 8 if (x % i == 0) { 9 while (x% i == 0){ 10 x/= i; 11 res^=(1<<(i-1)); 12 } 13 } 14 } 15 if (x != 1) { 16 res^=(1<<(x-1)); 17 } 18 return res; 19 } 20 int a[N]; 21 int main(){ 22 int n; 23 cin>>n; 24 long long ans = 0; 25 int pre = 0; 26 for(int i=1;i<=n;i++){ 27 cin>>a[i]; 28 int res = calc(a[i]); 29 pre^=res; 30 if(pre==0) 31 ans++; 32 ans+=mp[pre]; 33 mp[pre]+=1; 34 35 } 36 cout<<ans<<"\n"; 37 }

样例输入 #1

1 5
2 3 2 4 3 2
1 2

样例输出 #1

样例解释 #1

满⾜条件的 有 和 。

数据范围

子任务编号 数据点占比 1 20% 2 40% 3 40% 对于全部数据，保证有 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。