简答题
偏难
#21078
区间乘积 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有一个包含 n 个正整数的序列A=[a 1 ,a 2 ,...,a n ]。 小杨想知…
区间乘积
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一个包含 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>数量。
输入样例
输出样例
样例解释
满足条件的 <l,r> 有<3,3> 和<1,5>。
数据范围

对于全部数据,保证有1≤n≤105,1≤ai≤30。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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";
}</pre>
解析
一段区间积的真实值很显然我们无法求出来,那么就要通过完全平方数的性质进行转化。我们有结论:一个数是完全平方数,当且仅当这个数质因数分解后,所有质因子的指数都为偶数。那么,判定一个数是否为完全平方数,可以等价于判定它的所有素因子的指数是否为偶数。注意到a[i]<=30,那么a[i]中质因子的个数只有2,3,5,7,11,13,17,19,23,29共10个,可以用十位的二进制数进行表示,若a[i]中含有奇数个第x个质因子,则让二进制表示的第x位为1,否则为0。设这个十位二进制数为b[i],则问题转变为找到[l,r]满足b[l]b[l+1]b[l+2]…b[r]=0,区间的xor和是满足做差的性质的,进一步转化为sum[r]^sum[l-1]=0(sum数组为b数组的xor前缀和),也就是找l和r,满足sum[r]=sum[l-1],这一步可以先统计出sumi等于某一定值k的数量cnt,根据乘法原理,最终答案为cnt*(cnt-1)/2,而k的取值范围为[0~],可以使用类似桶排的方式统计。