[GESP202406 七级] 区间乘积
GESP编程共123题，本题是整站第1423题，已经有人完成了本题，加油！
题目描述
小杨有一个包含 n 个正整数的序列 A=[a1,a2,…,an]。
小杨想知道有多少对 ⟨l,r⟩(1≤l≤r≤n) 满足 al×al+1×…×ar 为完全平方数。
一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得 x=y×y。
输入格式
第一行包含一个正整数 n，代表正整数个数。
第二行包含 n 个正整数 ai，代表序列 A。
输出格式
输出一个整数，代表满足要求的 ⟨l,r⟩ 数量。
输入输出样例
输入 #1
5 3 2 4 3 2
输出 #1
2
说明/提示
样例解释
满足条件的 ⟨l,r⟩ 有 ⟨1,5⟩ 和 ⟨3,3⟩。
数据范围
| 子任务编号 | 数据点占比 | n | ai |
|---|---|---|---|
| 1 | 20% | ≤10^5 | 1≤ai≤2 |
| 2 | 40% | ≤100 | 1≤ai≤30 |
| 3 | 40% | ≤10^5 | 1≤ai≤30 |
别灰心，再试一次！
真题解析
【题目大意】
给定n个数的序列a，求有多少组[l,r]满足()，且a[l]*a[l+1]*a[l+2]*…*a[r]是完全平方数(n ≤ 105, a[i] ≤ 30)
【解题思路】
一段区间积的真实值很显然我们无法求出来，那么就要通过完全平方数的性质进行转化。我们有结论：一个数是完全平方数，当且仅当这个数质因数分解后，所有质因子的指数都为偶数。那么，判定一个数是否为完全平方数，可以等价于判定它的所有素因子的指数是否为偶数。注意到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]，这一步可以先统计出sum[i](0<=i<=n)等于某一定值k的数量cnt，根据乘法原理，最终答案为cnt*(cnt-1)/2，而k的取值范围为[0~],可以使用类似桶排的方式统计。
参考程序
本站题目仅供学习，GESP版权归CCF所有，如有侵权请联系删除。站长陈老师QQ及微信:208234。