题解：P10724 [GESP202406 七级] 区间乘积
bifanwen
·
·
题解
原题链接
简要题意：给定序列 \{a_n\}，求 1 \leq l \leq r \leq n 且 \prod \limits_{i = l}^r a_i 为完全平方数的个数。
### 算法一 暴力 40
考虑到直接算再验证肯定是不行的。由于完全平方数等价于“每个质因子幂次都是偶数”，所以实际上只需要验证每个质因子个数即可。
那么可以预处理前缀质因子个数的奇偶性（不关心有多少，只关心奇偶性），枚举后验证。$a_i$ 很小，$30$ 之内只有 $2,3,5,7,11,13,17,19,23,29$ 共 $10$ 个素数，时间复杂度 $\mathcal{O}(10n^2)$. $40 \text{pts}$.
### 算法二 正解 100
考虑一下 $a_i \leq 2$ 的情形。这时候我们只需要考虑一个质因子 $2$ 的奇偶情况。 $\forall 1 \leq i \leq n$, $\prod \limits_{j = 1}^i a_j$ 中 $2$ 的质因子要么是偶数，要么是奇数，用 $p_i = 0 \space 或 \space 1$ 表示。
注意到 $[l,r]$ 对答案有贡献当且仅当 $p_{l - 1} = p_r$. 由于我们只关心答案而不关心是哪些区间的贡献，只需要知道 $p_i$ 之间相等的情形，也就是有多少个 $i$ 使得 $p_i = 0$，有多少个 $p_i = 1$. 然后从中任选两个作为答案即可。
显然这扩展到 $a_i \leq 30$ 不太难。直接地，开一个 $0/1$ 的十维数组 $p$，每一维表示从小到大第几个素数的奇偶性情况，最后枚举 $p$ 统计即可。
有一个细节：十维都是 $0$ 的情况要初始化为 $1$，因为 $p_{l - 1} = p_r$ 的判断中可能访问到 $p_0$，如果没有初始化会导致 $l = 1$ 的答案被忽略掉。
另一个细节：答案最大会到 $\frac{n(n - 1)}{2}$，要开 $\text{long long}$.
代码实现虽然暴力，但足够简洁明白。
时间复杂度：$\mathcal{O}(10n)$. $100 \text{pts}$.
```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -f; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
typedef long long ll;
const int N = 1e5 + 1;
int n, f[11];
int p[2][2][2][2][2][2][2][2][2][2];
int main() {
read(n);
p[0][0][0][0][0][0][0][0][0][0] = 1;
for(int i = 1; i <= n; i++) {
int x; read(x);
while(x % 2 == 0) f[1] ^= 1, x /= 2;
while(x % 3 == 0) f[2] ^= 1, x /= 3;
while(x % 5 == 0) f[3] ^= 1, x /= 5;
while(x % 7 == 0) f[4] ^= 1, x /= 7;
while(x % 11 == 0) f[5] ^= 1, x /= 11;
while(x % 13 == 0) f[6] ^= 1, x /= 13;
while(x % 17 == 0) f[7] ^= 1, x /= 17;
while(x % 19 == 0) f[8] ^= 1, x /= 19;
while(x % 23 == 0) f[9] ^= 1, x /= 23;
while(x % 29 == 0) f[10] ^= 1, x /= 29;
// 暴力分解
p[f[1]][f[2]][f[3]][f[4]][f[5]][f[6]][f[7]][f[8]][f[9]][f[10]]++;
// 十维状态个数记录
}
ll Ans = 0;
for(int a = 0; a <= 1; a++)
for(int b = 0; b <= 1; b++)
for(int c = 0; c <= 1; c++)
for(int d = 0; d <= 1; d++)
for(int e = 0; e <= 1; e++)
for(int f = 0; f <= 1; f++)
for(int g = 0; g <= 1; g++)
for(int h = 0; h <= 1; h++)
for(int i = 0; i <= 1; i++)
for(int j = 0; j <= 1; j++) { // 枚举所有可能的奇偶状态
int t = p[a][b][c][d][e][f][g][h][i][j];
Ans += 1ll * t * (t - 1) / 2; // 任选 2 个的方案数
}
printf("%lld\n", Ans);
return 0;
}
```