GESP认证C++编程真题解析 | P10724 [GESP202406 七级] 区间乘积

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

---

【题目来源】

洛谷：[P10724 GESP202406 七级] 区间乘积 - 洛谷

【题目描述】

小杨有一个包含n nn个正整数的序列A = [ a 1 , a 2 , … , a n ] A=[a_1,a_2,\dots,a_n]A=[a1​,a2​,…,an​]。

小杨想知道有多少对< l , r > ( 1 ≤ l ≤ r ≤ n ) <l,r>(1\le l\le r\le n)<l,r>(1≤l≤r≤n)满足a l × a l + 1 × ⋯ × a r a_l\times a_{l+1}\times \dots \times a_ral​×al+1​×⋯×ar​为完全平方数。

一个正整数x xx为完全平方数当且仅当存在一个正整数y yy使得x = y × y x=y\times yx=y×y。

【输入】

第一行包含一个正整数n nn，代表正整数个数。

第二行包含n nn个正整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1​,a2​,…,an​，代表序列A AA。

【输出】

输出一个整数，代表满足要求的< l , r > <l,r><l,r>数量。

【输入样例】

5 3 2 4 3 2

【输出样例】

2

【算法标签】

《洛谷 P10724 区间乘积》 #数论# #前缀和# #位运算# #GESP# #2024#

【代码详解】

// 40分#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 定义int为long long类型intn,ans;// n: 数组长度, ans: 答案inta[100005][12];// a[i][0]存储原数，a[i][1..11]存储质因数分解结果intb[12]={0,0,2,3,5,7,11,13,17,19,23,29};// 前11个质数（从索引1开始）// 计算第k个数的质因数分解，并累加到前缀和中voidcalc(intk){intx=a[k][0];// 获取第k个数的原始值// 将前一个数的质因数分解结果复制到当前数for(inti=1;i<=11;i++){a[k][i]=a[k-1][i];}// 特殊处理x=1的情况if(x==1){a[k][1]+=2;// 1的特殊处理，将质数2的指数加2}// 对x进行质因数分解for(inti=2;i<=11;i++){// 不断除以质数b[i]，直到不能整除为止while(x%b[i]==0){x/=b[i];// 除以质因数a[k][i]++;// 对应质因数的指数加1}}}signedmain()// 由于#define int long long，所以用signed main{cin>>n;// 输入数组长度// 读取n个数并计算每个数的质因数分解前缀和for(inti=1;i<=n;i++){cin>>a[i][0];// 将输入的数存储在a[i][0]calc(i);// 计算第i个数的质因数分解}// 统计满足条件的子数组数量for(inti=1;i<=n;i++)// 子数组的右端点{for(intj=0;j<=i;j++)// 子数组的左端点-1（j=0表示从开始）{intf=0,s=0;// f: 是否不满足条件标志, s: 总指数和// 检查子数组a[j+1..i]是否满足条件for(intk=1;k<=11;k++){// 计算子数组中第k个质因数的总指数s+=a[i][k]-a[j][k];// 检查这个质因数的指数是否为奇数if((a[i][k]-a[j][k])%2){f=1;// 存在指数为奇数的质因数break;}}// 如果所有质因数的指数都是偶数，且总指数和不为0if(!f&&s){ans++;// 计数加1}}}cout<<ans<<endl;// 输出结果return0;}

// 100分#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long类型intn,x,y,ans;// n: 数字个数, x: 前缀异或和, y: 临时变量, ans: 答案inta[1<<11]={1};// a[state]: 状态为state的前缀数量，初始a[0]=1intb[11]={0,2,3,5,7,11,13,17,19,23,29};// 前10个质数（索引1-10）// 计算函数：返回y的质因数分解状态的二进制表示intcalc(){if(y==1)// 如果y等于1，返回0{return0;}ints=0;// 状态值，用二进制表示// 遍历前10个质数for(inti=1;i<=10;i++){intt=0,c=0;// t: 当前质数的状态位, c: 当前质数的指数计数// 对y进行质因数分解while(y%b[i]==0){y/=b[i];// 除以质因数c++;// 指数加1// 关键：只关心指数的奇偶性// 如果c是奇数，设置对应的状态位if(c%2){t=1<<i;// 第i位设为1}else{t=0;// 第i位设为0}}s+=t;// 累加状态}returns;// 返回状态值}signedmain()// 由于使用了#define int long long，所以main要改为signed{// 输入数字个数cin>>n;// 处理n个数字for(inti=1;i<=n;i++){// 输入当前数字cin>>y;// 计算：y = 输入的数字 ⊕ calc()的返回值// 注意：这里y既用作输入，又在calc()中被修改y=x^calc();// x是之前的前缀异或和// 统计答案：当前状态y出现的次数ans+=a[y]++;// 加上之前出现过的次数，然后计数加1// 更新前缀异或和x=y;}// 输出结果cout<<ans<<endl;return0;}

【运行结果】

5 3 2 4 3 2 2