P10724 [GESP202406 七级] 区间乘积，洛谷id：sxshm

题解

一、分析

看看标签：数论，再看题目：完全平方。这不是质因数分解的标配吗？继续看数据范围： 1 ≤ a i ≤ 30 1\leq a_i\leq 30 1≤ai​≤30。直接枚举走起！！！

二、思路

1.数据处理

我们可以先把每一个数质因数分解，然后记录每一个质因子出现的次数（而不是有没有出现），然后把每一个质因子出现的次数的奇偶性记录下来,做一个前缀和（因为要连乘），状压（我这个蒟蒻竟然用了状压）成一个数，存下来。

2.计算答案

2.1 问题

现在每个前缀和的质因子出现个数都变成了 0 / 1 0/1 0/1，所以只要判断两个前缀和的状压状态相同即可，可是难道我们要把所有数对都遍历一遍吗？显然不行，复杂度 O ( n 2 ) O(n^2) O(n2) 直接爆炸。那怎么办呢？

2.2 解决

明显我们计算下标 i i i 的时候，需要比较的是前面有几个状压状态和 i i i 相等的，有没有更快的方式呢？当然有！我用的是 STL 中的 map，用来记录前面每个状态出现的次数。这样代码就呼之欲出了。

三、代码

#include<bits/stdc++.h>
using namespace std;
int prime[12]={0,2,3,5,7,11,13,17,19,23,29};//枚举质数
int n;
struct num{
	int cnt[12]={0,0,0,0,0,0,0,0,0,0,0,0};//初始化
}a[100010],sumk[100010];
int sum[100010];
map<int,int>mp;//存状态出现的次数
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		int t=1;
		while(x && t<=10){//分解质因子
			if(x%prime[t]==0){
				x/=prime[t];
				a[i].cnt[t]++;
			}else t++;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=10;j++){//做一个前缀和
			sumk[i].cnt[j]+=sumk[i-1].cnt[j]+a[i].cnt[j];
			sumk[i].cnt[j]%=2;//记录奇偶性
		}
		for(int j=1;j<=10;j++){
			sum[i]|=(1<<(j-1))*sumk[i].cnt[j];//状压
		}
	}
	int cnt=0;
	mp[0]=1;//注意有可能有些本身就是完全平方数
	for(int i=1;i<=n;i++){
		if(mp[sum[i]]!=0){
			cnt+=mp[sum[i]];//记录答案
		}
		mp[sum[i]]++;//记录状态
	}
	printf("%d",cnt);
	return 0;
}

END、最后

上面的代码并不能 AC，只有 80 分。是哪里错了呢？送你几句真言：

十年OI一场空，不开 LONGLONG 见祖宗

十年OI两茫茫，不开 LONGLONG 就凉凉
顺便宣传一下洛谷主页

拜拜