自动搬运

查看原文

来自洛谷，原作者为

	Tomle bzd

搬运于2025-08-24 23:00:39，当前版本为作者最后更新于2024-07-19 11:07:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

一个月没写题解了，为了挽救估值，精心写了这篇题解。

本文有些冗长，可能会浪费您的时间，但可以对这道题有更清晰的理解。

约定

1. 下文中 $\bigoplus$ 表示异或。
2. 质数 $p$ 在 $a$ 中出现了 $x$ 次表示将 $a$ 分解质因数后，$p$ 一共出现了 $x$ 次。

思路

二进制表示

首先，我们把每个数 $a_i$ 分解质因数，显然，$a_i$ 为完全平方数当且仅当每个质数都出现了偶数次。

注意到本题 $1\le a_i\le30$，其中的质数只有 $2,3,5,7,11,13,17,19,23,29$，共 $10$ 个。我们不妨将 $1\sim30$ 中每个数用二进制表示：对于第 $i$ 个质数（第 $i$ 位），若它出现了奇数次，这个二进制数的第 $i$ 位为 $1$，若出现了偶数次，则为 $0$。

两数相乘的二进制表示

由于本题需要乘法，我们考虑当知道 $a$ 和 $b$ 的二进制表示 $x$ 与 $y$，如何求出 $ab$ 的二进制表示 $z$。对于第 $i$ 个质数 $p_i$，共有四种情况：

• $p_i$ 在 $a$ 中出现了偶数次，$x$ 的第 $i$ 位为 $0$。$p_i$ 在 $b$ 中出现了偶数次，$y$ 的第 $i$ 位为 $0$，则 $p_i$ 在 $ab$ 中出现了偶数次，$z$ 的第 $i$ 位为 $0$。

• $p_i$ 在 $a$ 中出现了偶数次，$x$ 的第 $i$ 位为 $0$。$p_i$ 在 $b$ 中出现了奇数次，$y$ 的第 $i$ 位为 $1$，则 $p_i$ 在 $ab$ 中出现了奇数次，$z$ 的第 $i$ 位为 $1$。

• $p_i$ 在 $a$ 中出现了奇数次，$x$ 的第 $i$ 位为 $1$。$p_i$ 在 $b$ 中出现了偶数次，$y$ 的第 $i$ 位为 $0$，则 $p_i$ 在 $ab$ 中出现了奇数次，$z$ 的第 $i$ 位为 $1$。

• $p_i$ 在 $a$ 中出现了奇数次，$x$ 的第 $i$ 位为 $1$。$p_i$ 在 $b$ 中出现了奇数次，$y$ 的第 $i$ 位为 $1$，则 $p_i$ 在 $ab$ 中出现了偶数次，$z$ 的第 $i$ 位为 $0$。

容易发现，以上每种情况其实都是在进行异或操作，推出 $z=x\bigoplus y$。

本题主要部分

对于本题，令 $b_i$ 为 $i$ 的二进制表示，我们要维护一个前缀异或和，也就是 $pre_i=\bigoplus_{j=1}^ib_{a_i}$ 或 $pre_i=pre_{i-1}\bigoplus b_{a_i}$，特别的，$pre_0=0$。

容易发现，区间 $[l,r]$ 满足答案当且仅当 $pre_r=pre_{l-1}$，当 $pre_r$ 和 $pre_{l-1}$ 为 $1$ 的位异或后相互抵消时，$[l,r]$ 中数的乘积才是完全平方数。

令 $cnt_i$ 表示二进制表示为 $i$ 的数的个数。我们从 $1\sim n$ 扫描每个数 $a_i$，右端点为 $i$ 满足条件的区间的个数为 $cnt_{pre_i}$，将其计入答案后更新 $cnt_{pre_i}$。

细节

1. $cnt$ 数组大小开到 $2^{10}$。
2. 先计入答案，后更新（ans += cnt[prexor]++;）。
3. $pre_0=0$，初始时 $cnt_0=1$。
4. 十年 OI 一场空，不开 【】 见祖宗！

代码

#include <bits/stdc++.h>
using namespace std;

int n, a[100005], b[35], prexor;
long long ans, cnt[1 << 10];
vector <int> prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

void read(int &a, int ch = 0) {
	while (!isdigit(ch = getchar()));
	for (a = 0; isdigit(ch); ch = getchar()) a = (a << 3) + (a << 1) + (ch ^ 48);
}
void prework() {
	// 预处理数组 b
	for (int i = 1; i <= 30; i++) {
		int j = i;
		for (int k = 0; k < 10; k++) {
			while (j % prime[k] == 0) {
				b[i] ^= 1 << k;
				j /= prime[k];
			}
		}
	}
}
int main() {
	prework();
	read(n);
	cnt[0] = 1;
	for (int i = 1; i <= n; i++) {
		read(a[i]);
		prexor ^= b[a[i]];
		ans += cnt[prexor]++;
	}
	cout << ans;
	return 0;
}

写在最后

本题思维难度和代码难度都一般，感觉评绿有点高了，应该是上位黄。

本人表达能力较差，简单的思路被写得很冗长，但将其底层逻辑刨析得较为透彻。

本人写文章偏向学术，有些内容可能晦涩难懂，欢迎在评论区指出。