题解：P10724 [GESP202406 七级] 区间乘积
luxiaomao
·
·
题解
P10724 简单数学题
Problem
给出长 n 的正整数序列 a_i，求出该序列中有多少个区间，满足该区间内所有数的乘积是完全平方数。
Solution
发现乘积会很大，我们考虑质因数分解（$a_i \le 30$，这个范围内只有十个质数），记 $cnt_{i,j}$ 为 $a_i$ 的质因子中有几个质数 $j$。
如果一个数 $a_i$ 是完全平方数，显然所有的 $cnt_{i,j}$ 都是偶数。
这个结论同样可以拓展到乘积，如果 $\prod\limits_{i=l}^ra_i$ 是完全平方数，所有的 $\sum\limits_{i = l}^ra_{i,j}$ 都是偶数。
考虑根据奇偶性进行前缀和，两个前缀和相同就为答案增加一个贡献。
如何快速判断前缀和是否相同？发现只有十个质数，那么我们简单状压一下就行了，当然暴力也不是不行，复杂度吃得消。
具体实现请看代码。
### Code
```cpp
#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int n,a[N];
int p[] = {114514,2,3,5,7,11,13,17,19,23,29},tot = 10;
int sum[N][15];
int cnt[1100],ans;
signed main()
{
scanf("%lld",&n);
for(int i = 1;i <= n;i++)
{
scanf("%lld",&a[i]);
for(int j = 1;j <= 10;j++)
while(a[i]%p[j] == 0)
sum[i][j]++,a[i]/=p[j];
}
cnt[0]++;
for(int i = 1;i <= n;i++)
{
int k = 0;
for(int j = 1;j <= 10;j++)
sum[i][j] += sum[i-1][j];
for(int j = 1;j <= 10;j++)
k = k*2 + sum[i][j]%2;
ans += cnt[k]++;
}
printf("%lld\n",ans);
return 0;
}
```