简答题 偏难
#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>数量。


输入样例

5
3 2 4 3 2

输出样例

2

样例解释

满足条件的 <l,r> 有<3,3> 和<1,5>。

数据范围

对于全部数据,保证有1≤n≤105,1≤ai≤30。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; map&lt;int,int&gt; mp; const int N = 1e5+10; int calc(int x) { int res = 0; for (int i = 2; i * i &lt;= x; i++) { if (x % i == 0) { while (x% i == 0){ x/= i; res^=(1&lt;&lt;(i-1)); } } } if (x != 1) { res^=(1&lt;&lt;(x-1)); } return res; } int a[N]; int main(){ int n; cin&gt;&gt;n; long long ans = 0; int pre = 0; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;a[i]; int res = calc(a[i]); pre^=res; if(pre==0) ans++; ans+=mp[pre]; mp[pre]+=1; } cout&lt;&lt;ans&lt;&lt;"\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~],可以使用类似桶排的方式统计。