思路
当一个数是完全平方数的时候，它的所有质因子的次数都是偶数。
记 \(x\) 的质因子为 \(p_1^{q1} \times p_2^{q2} \times p_3^{q3} ... \times p_v^{qv}\)。这些数可以通过次数的奇偶性用一个 \(v\) 位的二进制串 \(B\) 表示，\(B_i\) 为 \(0\) 说明 \(q_i\) 为偶数，\(B_i\) 为 \(1\) 说明 \(q_i\) 为奇数。比如 \(10 = 2^1 \times 3^0 \times 5^1\)，可以用二进制串 \(101\) 来表示。
如果有两个数 \(x\) 和 \(y\)，满足 \(x > y\)，它们的二进制串 \(B\) 相同，那么 \(x \div y\) 一定是完全平方数。记 \(t_i\) 为每个 \(a_i\) 的前缀积，\(b_i\) 为每个 \(a_i\) 的前缀积所对应的二进制串。对于每个 \(i\) 如果存在 \(k_i\) 个 \(x\) 满足 \(i > x\)，并且 \(b_i = b_x\)，那么就有 \(k_i\) 个以 \(i\) 为右端点的区间积为完全平方数。最终答案 \(ans = \sum_{i = 1}^{n} \ k_i\)
代码实现
可以先把每个到 \(i\) 的前缀积对应的 \(b_i\) 用字符串表示，再用 map 存储（想省时间其实也可以用 unordered_map）对于每个 \(i\)，满足条件的 \(x\) 的个数，即在 \(i\) 前面的二进制串等于 \(b_i\) 的数的个数。前缀积太大，不用高精度可能存不下，只需要存前缀积中每个质因子的指数就好了。
完整代码
#include<bits/stdc++.h>
using namespace std;
long long n, x, ans, cnt[11];
long long p[11] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; //30以内的所有质数(0是用来占位的)。
map<string, long long>t;//存储当前每个二进制串出现了几次。
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x;
if(x != 1) {
for (int i = 1; i <= 10; i++) //分解质因数。
while(x % p[i] == 0) {
x /= p[i];
cnt[i]++; //对应质因子的指数加一。
}
}
string str = "";
for (int i = 1; i <= 10; i++)
if(cnt[i] % 2) str += "1"; //奇数用1表示。
else str += "0" ; //偶数用0表示。
ans += t[str];
if(str == "0000000000") ans++;//完全平方数需要特判
t[str]++;
}
cout << ans << endl;
return 0;
}