题解：P10724 [GESP202406 七级] 区间乘积

· · 题解

题目传送门

题目大意

给出 n 个数 a_i，求有多少对 \lang l,r \rang，满足 1 \le l \le r \le n 且 a_l \times a_{l+1} \times \dots \times a_{r-1} \times a_r 为完全平方数。

一个正整数 x 为完全平方数，当且仅当存在一个正整数 y，使得 x = y^2。

思路讲解

阶段一：前缀积

首先，我们将问题进行一个类似前缀和的转化。

设 p_i 为 \prod_{j=1}^{i} a_j，即序列 A 前 i 个数的乘积，则题目可转换为存在多少对 \lang l,r \rang，满足 \frac{p_r}{p_{l-1}}(p_0 = 1) 为完全平方数。

阶段二：分解质因数

可是 p_i 最高可达到 30^{10^5}，存不下。需要再次优化。

学过奥数的朋友应该都知道，完全平方数的因数个数为奇数，反之亦然，因为它的平方根只能算一次。

而求出一个数因数个数，只需将它分解质因数后将所有质因数的指数先各自加 1 后相乘即可。因为它的因数都可以表述为它的若干个质因数的乘积（1 除外），所以每个质因数可以取走 0 到该质因数指数个（取走 0 个则作为 1 相乘，如果都不取则结果为 1）。

再回到题目，可以发现 a_i 的上限很小，只有 30，所以我们可以列出 30 以内的所有质数 2,3,5,7,11,13,17,19,23,29，并定义一个二维数组 s_{i,j}，表示序列 a 的前 i 个数的乘积分解质因数后第 j 个质数的指数为多少（如果为 0 则表示不存在）。

在给 s_{i,j} 赋值时，就可以统计 a_i 分解质因数后，第 j 个质数的指数（不存在为 0），再加上 s_{i-1,j} 的指数。在 p_{l-1} 和 p_r 进行相除时，只需将 s_r 的每一个 s_{r,i} 减去 s_{l-1} 的每一个 s_{l-1,j} 即可（1 \le i,j \le 10）。

判断是否为完全平方数时只需用上前面说的方法，将减后的指数加 1 并相乘，求出因数个数。如果因数为奇数个，则该数是完全平方数，否则不是。

这样我们就可以枚举所有的 \langle l,r \rangle，查看有多少个的乘积为完全平方数。算法复杂度为 O(n^2)。

阶段三：状态压缩+异或

如果要使所有质因数的指数加 $1$ 后的乘积为奇数，那乘积就不能含有质因子 $2$，所以所有质因数加 $1$ 后的结果必需为奇数，也就是说所有质因子的指数必需为偶数，所以我们只关心 $p_{r}$ 除以 $p_{l-1}$ 后所有的质因数的指数是否为偶数。 所以我们可以将 $s_{i,j}$ 压缩成 $s_i$，$s_i$ 从右往左数第 $j$ 个二进制位表示 $p_i$ 第 $j$ 个质数的指数模 $2$ 的余数（如果 $p_i$ 的质因数中不存在第 $j$ 个质数，则指数算作 $0$）。 可是 $s_i$ 如果直接相加可能会进位，该如何避免进位呢？ 按位异或相信大家都不陌生，在编程时可以用 `^` 来表示。它的运算规则为遍历每一个**二进制位**，如果不同则答案的这一位为 $1$，否则为 $0$。 不过，我们可以换一种方式来表示它的运算规则——相加但不进位。因为不管是按照依照原来的规则，还是新定义出来的规则，都不影响结果。 所以我们在算出 $a_i$ 的质因数后，就可让 $s_i$ 直接异或 $s_{i-1}$。 在 $p_r$ 和 $p_{l-1}$ 进行相除时，就可以直接将 $s_r$ 的每一位减去 $s_{l-1}$ 的每一位（如果不足则自己加上 $2$），如果每一位为 $0$，则说明 $s_r$ 和 $s_l$ 的质因子相减后每一位为偶数，即 $p_r \div p_{l-1}$ 为完全平方数，也就是说 $\lang l,r \rang$ 满足题目要求。 仔细观察，不难发现，如果$s_r$ 的每一位减去 $s_{l-1}$ 的每一位（如果不足则自己加上 $2$）后，每一位为 $0$，则说明 $s_r$ 和 $s_{l-1}$ 相等。 所以我们可以遍历右端点，并将答案加上前面所有和 $s_r$ 相等的 $s_{l-1}(l \le i)$ 的数量即可，统计 $s_j$ 的操作可以通过 `map` 实现。 注意，$l=1$ 时 $s_{l-1}$ 为 $0$，要提前加入 `map` 中。 算法复杂度为 $O(n \log{n})$。 # 代码实现 ```cpp #include <bits/stdc++.h> using namespace std; int prime[11]={0,2,3,5,7,11,13,17,19,23,29}; //统计小于30的质数 map<long long,long long> cnt; long long n,a[100005],s[100005],ans; int main(){ cin>>n; cnt[0]=1; for(int i=1;i<=n;i++){ cin>>a[i]; int tmp=0; for(int j=1;j<=10;j++){ //统计s[i] int sum=0; while(a[i]%prime[j]==0) sum++,a[i]/=prime[j]; tmp+=sum%2,tmp*=2;//赋值后左移一位 } s[i]=s[i-1]^tmp; ans+=cnt[s[i]]++; //统计前面出现多少次s[i],并将s[i]出现的次数加1 } cout<<ans; return 0; } ``` 完结撒花！